Dada una array arr[] de N enteros, la tarea es maximizar la suma de los números seleccionados sobre todas las operaciones, de modo que en cada operación, elija un número A i , elimine una aparición del mismo y elimine todas las apariciones de A i – 1 y A i + 1 (si existen) en la array hasta que la array se vacía.
Ejemplos:
Entrada: arr[] = {3, 4, 2}
Salida: 6
Explicación: En la primera operación, seleccione 4 y elimínelo. Por lo tanto, todas las apariciones de 3 y 5 se eliminan de arr[]. La array después de la operación es arr[] = {2}. En la segunda operación, seleccione 2. Por lo tanto, la suma de todos los números seleccionados = 4+2 = 6, que es el máximo posible.Entrada: arr[] = {2, 2, 3, 3, 3, 4}
Salida: 9
Explicación: En la primera operación, seleccione 3 y elimínelo. Por lo tanto, todas las apariciones de 2 y 4 se eliminan de arr[]. La array después de la operación es arr[] = {3, 3}. En la 2ª y 3ª operación, seleccione 3. Por lo tanto, la suma de todos los números seleccionados = 3+3+3 = 9, que es el máximo posible.
Enfoque: el problema dado se puede resolver contando la frecuencia de los elementos de la array y luego encontrar la suma máxima que se analiza en la publicación anterior de este artículo.
Complejidad de tiempo: O(M + F), donde M es el elemento máximo del arreglo y F es la frecuencia máxima de un elemento del arreglo .
Espacio Auxiliar: O(M), donde M es el elemento máximo del arreglo .
Enfoque de programación dinámica : el enfoque anterior también se puede optimizar y resolver mediante la programación dinámica . Se puede observar que si se selecciona un número A i del arreglo arr[] , contribuirá A i * freq[A i ] a la suma final. Usando esta observación, siga los pasos a continuación para resolver el problema dado:
- Cree una array freq[] , que almacene la frecuencia de cada elemento en la array arr[] .
- Cree una array 1D dp[] , donde dp[i] representa la suma máxima posible de los valores seleccionados que se encuentran en el rango [1, i] en la array dada.
- Para cada valor de i , hay dos casos posibles como sigue:
- Caso 1, donde se selecciona i . En este caso, el valor de dp[i] = freq[i] * i + dp[i-2] .
- Caso 2, donde se selecciona i – 1 . En este caso, el valor de dp[i] = dp[i-1] .
- Por lo tanto, la relación DP del problema anterior es:
dp[i] = max( dp[i – 1], (freq[i] * i)+ dp[i – 2]) para todos los valores de i en el rango [0, MAX] donde MAX es el entero máximo en arr []
- El valor almacenado en dp[MAX] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// cpp program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// selected numbers from an array to make
// the array empty
int maximizeSum(vector<int> arr)
{
// Edge Case
if (arr.size() == 0)
return 0;
// Stores the frequency of each element
// in the range [0, MAX] where MAX is
// the maximum integer in the array arr
int mx= *max_element(arr.begin(),arr.end());
int freq[mx + 1]={0};
// Loop to iterate over array arr[]
for (int i : arr)
freq[i] += 1;
// Stores the DP states
int dp[mx + 1]={0};
// Initially dp[1] = freq[1]
dp[1] = freq[1];
// Iterate over the range [2, MAX]
for (int i = 2; i < mx + 1; i++)
dp[i] = max(freq[i] * i + dp[i - 2],
dp[i - 1]);
// Return Answer
return dp[mx];
}
// Driver Code
int main()
{
vector<int> arr = {2, 2, 3, 3, 3, 4};
// Function Call
cout << (maximizeSum(arr));
}
// This code is contributed by amreshkumar3.
Java
// java program for the above approach
class GFG
{
// Utility function to find
// maximum value of an element in array
static int getMax(int [] arr)
{
int max = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] > max)
max = arr[i];
}
return max;
}
// Function to find the maximum sum of
// selected numbers from an array to make
// the array empty
static int maximizeSum(int [] arr)
{
// Edge Case
if (arr.length == 0)
return 0;
// Stores the frequency of each element
// in the range [0, MAX] where MAX is
// the maximum integer in the array arr
int max = getMax(arr);
int [] freq = new int[max + 1];
// Loop to iterate over array arr[]
for (int i : arr)
freq[i] += 1;
// Stores the DP states
int[] dp = new int[max + 1];
// Initially dp[1] = freq[1]
dp[1] = freq[1];
// Iterate over the range [2, MAX]
for (int i = 2; i < max + 1; i++)
dp[i] = Math.max(freq[i] * i + dp[i - 2],
dp[i - 1]);
// Return Answer
return dp[max];
}
// Driver Code
public static void main(String [] args)
{
int [] arr = { 2, 2, 3, 3, 3, 4 };
// Function Call
System.out.println((maximizeSum(arr)));
}
}
// This code is contributed by AR_Gaurav
Python3
# Python program for the above approach # Function to find the maximum sum of # selected numbers from an array to make # the array empty def maximizeSum(arr): # Edge Case if not arr: return 0 # Stores the frequency of each element # in the range [0, MAX] where MAX is # the maximum integer in the array arr freq = [0] * (max(arr)+1) # Loop to iterate over array arr[] for i in arr: freq[i] += 1 # Stores the DP states dp = [0] * (max(arr)+1) # Initially dp[1] = freq[1] dp[1] = freq[1] # Iterate over the range [2, MAX] for i in range(2, max(arr)+1): dp[i] = max(freq[i]*i + dp[i-2], dp[i-1]) # Return Answer return dp[max(arr)] # Driver Code arr = [2, 2, 3, 3, 3, 4] # Function Call print(maximizeSum(arr))
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG
{
// Function to find the maximum sum of
// selected numbers from an array to make
// the array empty
static int maximizeSum(int[] arr)
{
// Edge Case
if (arr.Length == 0)
return 0;
// Stores the frequency of each element
// in the range [0, MAX] where MAX is
// the maximum integer in the array arr
int[] freq = new int[(arr.Max() + 1)];
// Loop to iterate over array arr[]
foreach(int i in arr) freq[i] += 1;
// Stores the DP states
int[] dp = new int[(arr.Max() + 1)];
// Initially dp[1] = freq[1]
dp[1] = freq[1];
// Iterate over the range [2, MAX]
for (int i = 2; i < arr.Max() + 1; i++)
dp[i] = Math.Max(freq[i] * i + dp[i - 2],
dp[i - 1]);
// Return Answer
return dp[arr.Max()];
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 2, 3, 3, 3, 4 };
// Function Call
Console.WriteLine((maximizeSum(arr)));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum sum of
// selected numbers from an array to make
// the array empty
function maximizeSum(arr) {
// Edge Case
if (arr.length == 0)
return 0;
// Stores the frequency of each element
// in the range [0, MAX] where MAX is
// the maximum integer in the array arr
let freq = new Array(Math.max(...arr) + 1).fill(0);
// Loop to iterate over array arr[]
for (let i = 0; i < arr.length; i++)
freq[arr[i]] += 1
// Stores the DP states
let dp = new Array(Math.max(...arr) + 1).fill(0);
// Initially dp[1] = freq[1]
dp[1] = freq[1]
// Iterate over the range [2, MAX]
for (let i = 2; i <= Math.max(...arr) + 1; i++)
dp[i] = Math.max(freq[i] * i + dp[i - 2], dp[i - 1])
// Return Answer
return dp[Math.max(...arr)]
}
// Driver Code
let arr = [2, 2, 3, 3, 3, 4]
// Function Call
document.write(maximizeSum(arr))
// This code is contributed by Potta Lokesh
</script>
9
Complejidad temporal: O(M + F), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(M), donde M es el elemento máximo del arreglo .
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA