Dada una array arr[] , la tarea es encontrar la puntuación máxima de eliminación de un elemento donde cada elemento de la array se puede eliminar con la puntuación del elemento, pero la restricción es si eliminamos arr[i] , luego arr[ i] + 1 y arr[i] – 1 se eliminan automáticamente con 0 puntuaciones.
Ejemplos:
Entrada: arr[] = {7, 2, 1, 8, 3, 3, 6, 6}
Salida: 27
Explicación:
Paso 0: arr[] = 7 2 1 8 3 3 6 6, Puntuación: 0
Paso 1: arr[] = 7 1 8 3 6 6, Puntuación: 3
Paso 2: arr[] = 7 1 8 6 6, Puntuación: 6
Paso 3: arr[] = 7 8 6 6, Puntuación: 7
Paso 4: arr[ ] = 8 6 , Puntuación: 13
Paso 5: arr[] = 8 Puntuación: 19
Paso 6: arr[] = [] Puntuación:27
Entrada: arr[] = 1 2 3
Salida: 4
Enfoque: La idea es utilizar Programación Dinámica para resolver este problema. La observación clave del problema es que para eliminar cualquier elemento de la array, la ocurrencia del elemento y el valor en sí mismo es el factor importante.
Pongamos un ejemplo para entender la observación si la secuencia fuera 4 4 5. Entonces, tenemos dos opciones para elegir de 4 a 5. Ahora, al elegir 4, su puntuación sería 4*2 = 8. Por otro lado, si elegimos 5, su puntaje sería 5*1 = 5. Claramente, el puntaje máximo es 8.
Por lo tanto, para la secuencia anterior 4 4 5, freq[4] = 2 y freq[5] = 1.
Finalmente, para encontrar el puntaje óptimo, sería fácil primero dividir el problema en un problema más pequeño. En este caso, dividimos la secuencia en secuencias más pequeñas y encontramos una solución óptima para ella. Para la secuencia de números que contiene solo 0, la respuesta sería 0. De manera similar, si una secuencia contiene solo el número 0 y 1, entonces la solución sería cuenta[1]*1.
Relación de recurrencia:
dp[i] = max(dp[i – 1], dp[i – 2] + i*frecuencia[i])
Básicamente, tenemos 2 casos, ya sea para elegir un i -ésimo elemento y otro es para no elegir un i -ésimo elemento.
Caso 1: Si elegimos el i-ésimo elemento, la puntuación máxima hasta el i-ésimo elemento será dp[i-2] + i*freq[i] (elegir el i-ésimo elemento significa eliminar el (i-1)-ésimo elemento)
Caso 2: Si no elija el i-ésimo elemento, la puntuación máxima hasta el i-ésimo elemento será dp[i-1]
Ahora que tenemos que maximizar la puntuación, tomaremos el máximo de ambos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum score of the deleting a
// element from an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// score of the deleting an element
// from an array
int findMaximumScore(vector<int> a, int n)
{
// Creating a map to keep
// the frequency of numbers
unordered_map<int, int> freq;
// Loop to iterate over the
// elements of the array
for (int i = 0; i < n; i++) {
freq[a[i]]++;
}
// Creating a DP array to keep
// count of max score at ith element
// and it will be filled
// in the bottom Up manner
vector<int> dp(*max_element(a.begin(),
a.end())
+ 1,
0);
dp[0] = 0;
dp[1] = freq[1];
// Loop to choose the elements of the
// array to delete from the array
for (int i = 2; i < dp.size(); i++)
dp[i] = max(
dp[i - 1],
dp[i - 2] + freq[i] * i);
return dp[dp.size() - 1];
}
// Driver Code
int main()
{
int n;
n = 3;
vector<int> a{ 1, 2, 3 };
// Function Call
cout << findMaximumScore(a, n);
return 0;
}
Java
// Java implementation to find the
// maximum score of the deleting a
// element from an array
import java.util.*;
class GFG{
// Function to find the maximum
// score of the deleting an element
// from an array
static int findMaximumScore(int []a, int n)
{
// Creating a map to keep
// the frequency of numbers
@SuppressWarnings("unchecked")
HashMap<Integer,
Integer> freq = new HashMap();
// Loop to iterate over the
// elements of the array
for(int i = 0; i < n; i++)
{
if(freq.containsKey(a[i]))
{
freq.put(a[i],
freq.get(a[i]) + 1);
}
else
{
freq.put(a[i], 1);
}
}
// Creating a DP array to keep
// count of max score at ith element
// and it will be filled
// in the bottom Up manner
int []dp = new int[Arrays.stream(a).max().getAsInt() + 1];
dp[0] = 0;
dp[1] = freq.get(1);
// Loop to choose the elements of the
// array to delete from the array
for(int i = 2; i < dp.length; i++)
dp[i] = Math.max(dp[i - 1],
dp[i - 2] +
freq.get(i) * i);
return dp[dp.length - 1];
}
// Driver Code
public static void main(String[] args)
{
int n;
n = 3;
int []a = { 1, 2, 3 };
// Function call
System.out.print(findMaximumScore(a, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find the # maximum score of the deleting a # element from an array from collections import defaultdict # Function to find the maximum # score of the deleting an element # from an array def findMaximumScore(a, n): # Creating a map to keep # the frequency of numbers freq = defaultdict (int) # Loop to iterate over the # elements of the array for i in range (n): freq[a[i]] += 1 # Creating a DP array to keep # count of max score at ith element # and it will be filled # in the bottom Up manner dp = [0] * (max(a) + 1) dp[0] = 0 dp[1] = freq[1] # Loop to choose the elements of the # array to delete from the array for i in range (2, len(dp)): dp[i] = max(dp[i - 1], dp[i - 2] + freq[i] * i) return dp[- 1] # Driver Code if __name__ == "__main__": n = 3 a = [1, 2, 3] # Function Call print(findMaximumScore(a, n)) # This code is contributed by Chitranayal
C#
// C# implementation to find the
// maximum score of the deleting a
// element from an array
using System;
using System.Linq;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// score of the deleting an element
// from an array
static int findMaximumScore(int []a, int n)
{
// Creating a map to keep
// the frequency of numbers
Dictionary<int,
int> freq = new Dictionary<int,
int>();
// Loop to iterate over the
// elements of the array
for(int i = 0; i < n; i++)
{
if(freq.ContainsKey(a[i]))
{
freq[a[i]] = freq[a[i]] + 1;
}
else
{
freq.Add(a[i], 1);
}
}
// Creating a DP array to keep
// count of max score at ith element
// and it will be filled
// in the bottom Up manner
int []dp = new int[a.Max() + 1];
dp[0] = 0;
dp[1] = freq[1];
// Loop to choose the elements of the
// array to delete from the array
for(int i = 2; i < dp.Length; i++)
dp[i] = Math.Max(dp[i - 1],
dp[i - 2] +
freq[i] * i);
return dp[dp.Length - 1];
}
// Driver Code
public static void Main(String[] args)
{
int n;
n = 3;
int []a = { 1, 2, 3 };
// Function call
Console.Write(findMaximumScore(a, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the
// maximum score of the deleting a
// element from an array
// Function to find the maximum
// score of the deleting an element
// from an array
function findMaximumScore(a,n)
{
// Creating a map to keep
// the frequency of numbers
let freq = new Map();
// Loop to iterate over the
// elements of the array
for(let i = 0; i < n; i++)
{
if(freq.has(a[i]))
{
freq.set(a[i],
freq.get(a[i]) + 1);
}
else
{
freq.set(a[i], 1);
}
}
// Creating a DP array to keep
// count of max score at ith element
// and it will be filled
// in the bottom Up manner
let dp = new Array(Math.max(...a)+1);
dp[0] = 0;
dp[1] = freq.get(1);
// Loop to choose the elements of the
// array to delete from the array
for(let i = 2; i < dp.length; i++)
dp[i] = Math.max(dp[i - 1],
dp[i - 2] +
freq.get(i) * i);
return dp[dp.length - 1];
}
// Driver Code
let n = 3;
let a=[1, 2, 3];
// Function call
document.write(findMaximumScore(a, n));
// This code is contributed by avanitrachhadiya2155
</script>
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por deepak19engg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA