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) = 6Entrada: 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++
// 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
// 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.
Python3
# 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#
// 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
// 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
Publicación traducida automáticamente
Artículo escrito por yashgaherwar2002 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA