Dada una array de enteros positivos arr[] de tamaño N , la tarea es encontrar la suma máxima de una subsecuencia con la restricción de que ningún número de 2 en la secuencia debe ser adyacente al valor, es decir, si arr[i] se toma en la respuesta , entonces no se pueden seleccionar las ocurrencias de arr[i]-1 ni arr[i]+1 .
Ejemplos:
Entrada: arr[] = {2, 2, 2}
Salida: 6
Explicación:
La subsecuencia de suma máxima será [2, 2, 2] ya que no contiene ninguna ocurrencia de 1 o 3. Por lo tanto, suma = 2 + 2 + 2 = 6Entrada: arr[] = {2, 2, 3}
Salida: 4
Explicación:
Subsecuencia 1: [2, 2] ya que no contiene ninguna ocurrencia de 1 o 3. Por lo tanto, suma = 2 + 2 = 4
Subsecuencia 2: [ 3] ya que no contiene ninguna ocurrencia de 2 o 4. Por lo tanto, suma = 3
Por lo tanto, la suma máxima = 4
Enfoque de la solución: la idea es usar Programación Dinámica , similar a este artículo.
- Cree un mapa para almacenar el número de veces que aparece el elemento i en la secuencia.
- Para encontrar la respuesta, sería fácil primero dividir el problema en problemas más pequeños. En este caso, divide la secuencia en secuencias más pequeñas y encuentra una solución óptima para ella.
- Para la secuencia de números que contiene solo 0, la respuesta sería 0. De manera similar, si una secuencia contiene solo los números 0 y 1, entonces la solución sería contar[1]*1.
- Ahora construya una solución recursiva a este problema. Para una secuencia de números que contiene solo los números, 0 a n, la elección es elegir el elemento N-ésimo o no.
dp[i] = max(dp[i – 1], dp[i – 2] + i*freq[i] )
dp[i-1] representa no elegir el i-ésimo número, entonces el número anterior puede ser considerado.
dp[i – 2] + i*freq[i] representa elegir el i-ésimo número, luego el número antes de que sea eliminado. Por lo tanto, se considera el número anterior.
C++
// C++ program to find maximum sum
// subsequence with values
// differing by at least 2
#include <bits/stdc++.h>
using namespace std;
// function to find maximum sum
// subsequence such that two
// adjacent values elements are
// not selected
int get_max_sum(int arr[], int n)
{
// map to store the frequency
// of array elements
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}
// make a dp array to store
// answer upto i th value
int dp[100001];
memset(dp, 0, sizeof(dp));
// base cases
dp[0] = 0;
dp[1] = freq[0];
// iterate for all possible
// values of arr[i]
for (int i = 2; i <= 100000; i++) {
dp[i] = max(dp[i - 1],
dp[i - 2] + i * freq[i]);
}
// return the last value
return dp[100000];
}
// Driver function
int main()
{
int N = 3;
int arr[] = { 2, 2, 3 };
cout << get_max_sum(arr, N);
return 0;
}
Java
// Java program to find maximum sum
// subsequence with values
// differing by at least 2
import java.util.*;
import java.lang.*;
class GFG{
// Function to find maximum sum
// subsequence such that two
// adjacent values elements are
// not selected
public static int get_max_sum(int arr[], int n)
{
// map to store the frequency
// of array elements
HashMap<Integer,
Integer> freq = new HashMap<Integer,
Integer>();
for(int i = 0; i < n; i++)
{
if (freq.containsKey(arr[i]))
{
int x = freq.get(arr[i]);
freq.replace(arr[i], x + 1);
}
else
freq.put(arr[i], 1);
}
// Make a dp array to store
// answer upto i th value
int[] dp = new int[100001];
for(int i = 0; i < 100001; i++)
dp[i] = 0;
// Base cases
dp[0] = 0;
if (freq.containsKey(0))
dp[1] = freq.get(0);
else
dp[1] = 0;
// Iterate for all possible
// values of arr[i]
for(int i = 2; i <= 100000; i++)
{
int temp = (freq.containsKey(i)) ?
freq.get(i) : 0;
dp[i] = Math.max(dp[i - 1],
dp[i - 2] + i * temp);
}
// Return the last value
return dp[100000];
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int arr[] = { 2, 2, 3 };
System.out.println(get_max_sum(arr, N));
}
}
// This code is contributed by grand_master
Python3
# Python3 program to find maximum sum # subsequence with values # differing by at least 2 from collections import defaultdict # Function to find maximum sum # subsequence such that two # adjacent values elements are # not selected def get_max_sum(arr, n): # Map to store the frequency # of array elements freq = defaultdict(lambda : 0) for i in range(n): freq[arr[i]] += 1 # Make a dp array to store # answer upto i th value dp = [0] * 100001 # Base cases dp[0] = 0 dp[1] = freq[0] # Iterate for all possible # values of arr[i] for i in range(2, 100000 + 1): dp[i] = max(dp[i - 1], dp[i - 2] + i * freq[i]) # Return the last value return dp[100000] # Driver code N = 3 arr = [ 2, 2, 3 ] print(get_max_sum(arr, N)) # This code is contributed by stutipathak31jan
C#
// C# program to find maximum sum
// subsequence with values
// differing by at least 2
using System;
using System.Collections.Generic;
class GFG{
// Function to find maximum sum
// subsequence such that two
// adjacent values elements are
// not selected
public static int get_max_sum(int []arr, int n)
{
// map to store the frequency
// of array elements
Dictionary<int,
int> freq = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
{
if (freq.ContainsKey(arr[i]))
{
int x = freq[arr[i]];
freq[arr[i]]= x + 1;
}
else
freq.Add(arr[i], 1);
}
// Make a dp array to store
// answer upto i th value
int[] dp = new int[100001];
for(int i = 0; i < 100001; i++)
dp[i] = 0;
// Base cases
dp[0] = 0;
if (freq.ContainsKey(0))
dp[1] = freq[0];
else
dp[1] = 0;
// Iterate for all possible
// values of arr[i]
for(int i = 2; i <= 100000; i++)
{
int temp = (freq.ContainsKey(i)) ?
freq[i] : 0;
dp[i] = Math.Max(dp[i - 1],
dp[i - 2] + i * temp);
}
// Return the last value
return dp[100000];
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
int []arr = { 2, 2, 3 };
Console.WriteLine(get_max_sum(arr, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to find maximum sum
// subsequence with values
// differing by at least 2
// function to find maximum sum
// subsequence such that two
// adjacent values elements are
// not selected
function get_max_sum(arr, n)
{
// map to store the frequency
// of array elements
var freq = new Map();
for (var i = 0; i < n; i++) {
if(freq.has(arr[i]))
freq.set(arr[i], freq.get(arr[i])+1)
else
freq.set(arr[i], 1)
}
// make a dp array to store
// answer upto i th value
var dp = Array(100001).fill(0);
// base cases
dp[0] = 0;
dp[1] = (freq.has(0)?freq.get(0):0);
// iterate for all possible
// values of arr[i]
for (var i = 2; i <= 100000; i++) {
dp[i] = Math.max(dp[i - 1],
dp[i - 2] + i * (freq.has(i)?freq.get(i):0));
}
// return the last value
return dp[100000];
}
// Driver function
var N = 3;
var arr = [2, 2, 3];
document.write( get_max_sum(arr, N));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)