Subsecuencia de suma máxima con valores que difieren en al menos 2

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 = 6

Entrada: 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. 

1. Cree un mapa para almacenar el número de veces que aparece el elemento i en la secuencia.
2. 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.
3. 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.
4. 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++ 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 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 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# 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

<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>

4

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)