Reduzca la array y maximice la suma eliminando una ocurrencia de A[i] y todas las ocurrencias de A[i]+1 y A[i]-1

Dado un arreglo A[] que tiene N enteros positivos, la tarea es realizar las siguientes operaciones y maximizar la suma obtenida al reducir el arreglo:

• Seleccione un elemento de array (digamos A[i] ) y elimine una ocurrencia de ese elemento y agregue A[i] a la suma.
• Elimine todas las apariciones de A[i]-1 y A[i]+1 .
• Realice estas operaciones hasta que la array esté vacía.

Ejemplos:

Entrada: A[] = {3, 4, 2}
Salida: 6
Explicación: Primero, elimine el número 4 para sumar 4 a la suma y, en consecuencia, también se elimina el 3.
 Después de eso, la array A = [2]. 
Luego eliminamos el número 2 y agregamos 2.
La array se vacía, es decir, la array A = [].
Y por lo tanto suma total = (4 + 2) = 6

Entrada: A[] = {2, 2, 3, 3, 3, 4}
Salida: 9
Explicación: Primero, elimine el número 3 para agregar 3. Y todos los números de 2 y 4 también se eliminan. 
Después de eso, la array es A = [3, 3]. 
Luego elimine el número 3 nuevamente para agregar 3 puntos. Suma = 3 + 3 = 6.
La array ahora es A = [3].
En la última operación, elimine el número 3 una vez más para agregar 3. Suma = 6 + 3 = 9.
Ahora la array se vuelve vacía.
Por lo tanto, la suma máxima obtenida es 9.

Enfoque ingenuo: el enfoque ingenuo es tratar de reducir la array de todas las formas posibles, es decir, para cualquier valor (por ejemplo, A[i] ) que se pueda seleccionar y se pueda eliminar una ocurrencia de ese elemento o cualquier otro elemento que tenga una diferencia de 1 con A[i] se puede seleccionar (si está presente en la array) y se puede eliminar una aparición de eso.

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

Enfoque Eficiente: Este problema se puede resolver usando Programación Dinámica basada en la siguiente idea:

Si un elemento x se elimina una vez, todas las apariciones de x-1 y x+1 se eliminarán de la array.

• Por lo tanto, si se consideran todos los elementos de la array que tienen un valor desde 0 hasta x , entonces la suma máxima hasta x depende de la suma máxima hasta x-2 y la suma máxima hasta x-1 , es decir, si se incluye x, entonces x-1 no se puede incluir y viceversa. . [No es necesario considerar x+1 o x+2 porque aquí la iteración es del lado del valor inferior al lado del valor superior]
• Supongamos que estos valores máximos para cada x se almacenan en una array (por ejemplo , dp[] ), luego dp[x] = max(dp[x-1], dp[x-2]+x*ocurrences of x) .

Siga la ilustración a continuación para una mejor comprensión.

Ilustración:

Considere una array A[] = {2, 2, 3, 3, 3, 4}

Entonces la frecuencia de los elementos será:
freq = {{2 -> 2}, {3 -> 3}, {4 -> 1}}

El máximo de array es 4.
Por lo tanto, la array dp[] tendrá un tamaño de 5.
La array dp[] será {0, 0, 0, 0, 0}

Para x = 2:
        => dp[2] = max(dp[1], dp[0] + frec[2]*2)
                       = max(0, 2*2) = max(0, 0 + 4) = 4
        => pd[] = {0, 0, 4, 0, 0}

Para x = 3:
        => dp[3] = max(dp[2], dp[1] + frec[3]*3)
                       = max(4, 0 + 3*3) = max(0, 9) = 9
        => pd[] = {0, 0, 4, 9, 0}

Para x = 4:
        => dp[4] = max(dp[3], dp[2] + frec[4]*4)
                       = max(9, 4 + 4*1) = max(9, 8) = 9
        => pd[] = {0, 0, 4, 9, 9}

Entonces la respuesta es dp[4] = 9 que es la suma máxima posible

Siga los pasos mencionados a continuación para implementar la observación anterior:

• Cree un mp unordered_map para almacenar la frecuencia de cada elemento de la array.
• Calcule el valor máximo de la array (digamos max_val ).
• Cree una array dp[] para almacenar los valores máximos como en la observación e inicialice dp[1] como conteo de 1s.
• Iterar desde i = 2 hasta max_val :
  • Calcule el dp[i] como se mencionó anteriormente.
• Devuelve el dp[max_val] después de todas las iteraciones como respuesta porque contiene la suma máxima posible.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return Maximum number
// of points that can be earned
int MaximumPoints(int A[], int array_size)
{
    // Maximum element in array A
    int element_max = *max_element(A, A
                                          + array_size);
    unordered_map<int, int> mp;
 
    // Dp array for storing points
    int dp[element_max + 1] = { 0 };
 
    // Storing frequency of integers
    for (int i = 0; i < array_size; i++) {
        mp[A[i]]++;
    }
 
    dp[0] = 0;
    dp[1] = mp[1];
 
    // Calculation for getting maximum sum
    // in dp[] array at every steps
    for (int i = 2; i <= element_max; i++) {
        dp[i] = max(dp[i - 1],
                    dp[i - 2] + mp[i] * i);
    }
 
    // Returning the maximum sum
    return dp[element_max];
}
 
int main()
{
    int A[] = { 2, 2, 3, 3, 3, 4 };
 
    // Size of Array
    int array_size = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << MaximumPoints(A, array_size);
    return 0;
}

// Java program to implement the approach
import java.util.*;
import java.util.Arrays;
 
public class GFG {
  // Function to return Maximum number
  // of points that can be earned
  static int MaximumPoints(int A[], int array_size)
  {
    // Maximum element in array A
    int element_max =Arrays.stream(A).max().getAsInt();
    HashMap<Integer, Integer> mp = new HashMap<>();
 
    // Dp array for storing points
    int dp[] = new int[element_max + 1];
 
    // Storing frequency of integers
    for (int i = 0; i < array_size; i++) {
      if(mp.containsKey(A[i])){
        mp.put(A[i], mp.get(A[i]) + 1);
      }
      else{
        mp.put(A[i], 1);
      }
    }
 
    dp[0] = 0;
    if(mp.containsKey(1))
      dp[1] = mp.get(1);
 
    // Calculation for getting maximum sum
    // in dp[] array at every steps
    for (int i = 2; i <= element_max; i++) {
      dp[i] = Math.max(dp[i - 1],
                       dp[i - 2] + mp.get(i) * i);
    }
 
    // Returning the maximum sum
    return dp[element_max];
  }
 
  // Driver Code
  public static void main (String[] args) {
    int A[] = { 2, 2, 3, 3, 3, 4 };
 
    // Size of Array
    int array_size = A.length;
 
    // Function call
    System.out.print(MaximumPoints(A, array_size));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program to implement the approach
 
# Function to return Maximum number
# of points that can be earned
def MaximumPoints(A, array_size):
 
    # Maximum element in array A
    element_max = max(A)
    mp = {}
 
    # Dp array for storing points
    dp = [0 for i in range(element_max + 1)]
 
    # Storing frequency of integers
    for i in range(array_size):
 
        if (A[i] in mp):
            mp[A[i]] = mp[A[i]] + 1
        else:
            mp[A[i]] = 1
 
    if(1 in mp):
        dp[1] = mp[1]
 
    # Calculation for getting maximum sum
    # in dp[] array at every steps
    for i in range(2,element_max+1):
        dp[i] = (max(dp[i - 1], dp[i - 2] + mp[i] * i))
         
    # Returning the maximum sum
    return dp[element_max]
 
A = [ 2, 2, 3, 3, 3, 4 ]
 
# Size of Array
array_size = len(A)
 
# Function call
print(MaximumPoints(A, array_size))
 
# This code is contributed by shinjanpatra

// C# code to implement the approach
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG
{
 
  // Function to return Maximum number
  // of points that can be earned
  static int MaximumPoints(int[] A, int array_size)
  {
    // Maximum element in array A
    int element_max = A.Max();
    Dictionary<int, int> mp
      = new Dictionary<int, int>();
 
    // Dp array for storing points
    int[] dp = new int[element_max + 1];
 
    // Storing frequency of integers
    for (int i = 0; i < array_size; i++) {
      if (mp.ContainsKey(A[i])) {
        mp[A[i]] += 1;
      }
      else {
        mp[A[i]] = 1;
      }
    }
 
    dp[0] = 0;
    if (mp.ContainsKey(1))
      dp[1] = mp[1];
 
    // Calculation for getting maximum sum
    // in dp[] array at every steps
    for (int i = 2; i <= element_max; i++) {
      dp[i] = Math.Max(dp[i - 1],
                       dp[i - 2] + mp[i] * i);
    }
 
    // Returning the maximum sum
    return dp[element_max];
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int[] A = { 2, 2, 3, 3, 3, 4 };
 
    // Size of Array
    int array_size = A.Length;
 
    // Function call
    Console.Write(MaximumPoints(A, array_size));
  }
}
 
// This code is contributed by phasing17.

// JavaScript program to implement the approach
 
// Function to return Maximum number
// of points that can be earned
function MaximumPoints(A, array_size)
{
    // Maximum element in array A
    var element_max = Math.max(... A);
    mp = {};
 
    // Dp array for storing points
    var dp = [];
 
    // Storing frequency of integers
    for (var i = 0; i < array_size; i++) {
 
        if (mp.hasOwnProperty(A[i]))
            mp[A[i]] = mp[A[i]] + 1;
        else {
            mp[A[i]] = 1;
        }
    }
 
    dp.push(0);
    if (dp.hasOwnProperty(1))
        dp.push(mp[1]);
    else
        dp.push(0);
    // Calculation for getting maximum sum
    // in dp[] array at every steps
    for (var i = 2; i <= element_max; i++) {
        dp.push(Math.max(dp[i - 1], dp[i - 2] + mp[i] * i));
    }
    // Returning the maximum sum
    return dp[element_max];
}
 
var A = [ 2, 2, 3, 3, 3, 4 ];
 
// Size of Array
var array_size = A.length;
 
// Function call
console.log(MaximumPoints(A, array_size));
 
// this code was contributed by phasing17

9

Complejidad temporal: O(N) 
Espacio auxiliar: O(M) donde M es el elemento máximo del arreglo