Dada una array A[] de N números, necesitamos maximizar la suma de los números seleccionados siguiendo la operación dada:
- En cada paso, debe seleccionar un número A i , eliminar una ocurrencia y agregarla a la suma.
- Elimine una ocurrencia de A i -1 y A i +1 (si existen en la array).
- Repita estos pasos hasta que la array se vacíe.
Ejemplos:
Entrada: A[] = {1, 2, 3}
Salida: 4
Explicación: En el primer paso seleccionamos 1, entonces 1 y 2 se eliminan de la secuencia dejándonos con 3.
Luego seleccionamos 3 de la secuencia y lo eliminamos.
Entonces la suma de los números seleccionados es 1+3 = 4.Entrada: A[] = {1, 2, 2, 2, 3, 4}
Salida: 10
Explicación: Seleccione uno de los 2 de la array.
Entonces 2, 2-1, 2+1 serán eliminados.
Ahora la array es {2, 2, 4}, ya que se eliminan 1 y 3.
Seleccione 2 en los próximos dos pasos y luego seleccione 4 en el último paso.
Obtenemos una suma de 2 + 2 + 2 + 4 = 10 que es el máximo posible.
Planteamiento: La idea para resolver el problema es:
Calcule previamente la ocurrencia de todos los números (digamos x ) en la array A[] y luego itere desde el número máximo hasta el número mínimo.
Para cada número x, elimine una ocurrencia de x y x-1 (si existe) y agregue x a la suma hasta que x se elimine por completo.
Siga los pasos mencionados a continuación para resolver el problema
- Calcule el valor MAX en la array.
- Cree una array de tamaño MAX y almacene las ocurrencias de cada elemento en ella.
- Como queremos maximizar nuestra respuesta, comenzaremos a iterar desde el valor MAX hasta 0.
- Si la ocurrencia del i- ésimo elemento es mayor que 0, entonces agréguelo a nuestra respuesta, disminuya las ocurrencias del i-1- ésimo elemento en 1, y también disminuya la ocurrencia del i -ésimo en 1 ya que lo hemos agregado a nuestra respuesta. .
- No tenemos que disminuir la aparición del elemento i+1 th porque ya estamos comenzando desde el final, por lo que i+1 th ya está procesado.
- Puede haber múltiples apariciones del i- ésimo elemento, por eso no disminuya i todavía, para permanecer en el mismo elemento.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to Maximize the sum of selected
// numbers by deleting three consecutive numbers.
#include <bits/stdc++.h>
using namespace std;
// function to maximize the sum of selected numbers
int maximizeSum(int arr[], int n) {
// Largest element in the array
int mx = -1;
for(int i = 0; i < n; i++)
{
mx = max(mx, arr[i]);
}
// An array to count the occurrence of each element
int freq[mx + 1];
memset(freq, 0, sizeof(freq));
for(int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// ans to store the result
int ans = 0, i=mx;
// Using the above mentioned approach
while(i>0){
// if occurrence is greater than 0
if(freq[i] > 0){
// add it to ans
ans += i;
// decrease i-1th element by 1
freq[i-1]--;
// decrease ith element by 1
freq[i]--;
}else{
// decrease i
i--;
}
}
return ans;
}
// Driver code
int main()
{
int a[] = {1, 2, 3};
int n = sizeof(a) / sizeof(a[0]);
cout << maximizeSum(a, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
import java.math.*;
class GFG
{
// Function to maximise the sum of selected numbers
//by deleting occurrences of Ai-1 and Ai+1
public static int getMaximumSum (int arr[]) {
// Number of elements in the array
int n = arr.length;
// Largest element in the array
int max = -1;
for(int i = 0; i < n; i++)
{
max = Math.max(max, arr[i]);
}
// An array to count the occurrence of each element
int []freq = new int[max + 1];
for(int i = 0; i < n; i++)
{
freq[arr[i]]++;
}
// ans to store the result
int ans = 0, i=max;
// Using the above mentioned approach
while(i>0){
// if occurrence is greater than 0
if(freq[i] > 0){
// add it to ans
ans += i;
// decrease i-1th element by 1
freq[i-1]--;
// decrease ith element by 1
freq[i]--;
}else{
// decrease i
i--;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int []a = {1, 2, 3};
System.out.println(getMaximumSum(a));
}
}
Python3
# Python3 program to Maximize the sum of selected # numbers by deleting three consecutive numbers. # function to maximize the sum of # selected numbers def maximizeSum(a, n) : # maximum in the sequence maximum = max(a) # stores the occurrences of the numbers ans = dict.fromkeys(range(0, n + 1), 0) # marks the occurrence of every # number in the sequence for i in range(n) : ans[a[i]] += 1 # ans to store the result result = 0 i = maximum # Using the above mentioned approach while i > 0: # if occurrence is greater than 0 if ans[i] > 0: # add it to ans result += i; # decrease i-1th element by 1 ans[i-1] -= 1; # decrease ith element by 1 ans[i] -= 1; else: # decrease i i -= 1; return result; # Driver code if __name__ == "__main__" : a = [1, 2, 3] n = len(a) print(maximizeSum(a, n)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
using System.Linq;
class GFG
{
// Function to maximise the sum of selected numbers
//by deleting occurrences of Ai-1 and Ai+1
static int getMaximumSum(int []arr)
{
// Number of elements in the array
int n = arr.Length;
// Largest element in the array
int max = arr.Max();
// An array to count the occurrence of each element
int []freq = new int[max + 1];
for(int j = 0; j < n; j++)
{
freq[arr[j]]++;
}
// ans to store the result
int ans = 0, i=max;
// Using the above mentioned approach
while(i>0){
// if occurrence is greater than 0
if(freq[i] > 0){
// add it to ans
ans += i;
// decrease i-1th element by 1
freq[i-1]--;
// decrease ith element by 1
freq[i]--;
}else{
// decrease i
i--;
}
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
int []a = {1, 2, 3};
Console.Write(getMaximumSum(a));
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript implementation of the approach
// Function to maximise the sum of selected numbers
//by deleting occurrences of Ai-1 and Ai+1
function getMaximumSum(arr)
{
// Number of elements in the array
let n = arr.length;
// Largest element in the array
let max = Number.MIN_VALUE;
for(let i = 0; i < n; i++)
{
max = Math.max(max, arr[i]);
}
// An array to count the occurrence of each element
let freq = new Array(max + 1);
freq.fill(0);
for(let j = 0; j < n; j++)
{
freq[arr[j]]++;
}
// ans to store the result
let ans = 0, i=max;
// Using the above mentioned approach
while(i>0){
// if occurrence is greater than 0
if(freq[i] > 0){
// add it to ans
ans += i;
// decrease i-1th element by 1
freq[i-1]--;
// decrease ith element by 1
freq[i]--;
}else{
// decrease i
i--;
}
}
return ans;
}
let a = [1, 2, 3];
document.write(getMaximumSum(a));
// This code is contributed by suresh07.
</script>
Producción:
4
Complejidad de tiempo: (A max + Mayor ocurrencia de elemento en arr), porque si la frecuencia es mayor que 1, entonces estamos procesando ese elemento varias veces.
Espacio Auxiliar: O(A max ), donde A max es el elemento máximo presente en el arreglo A[].