Dada una array arr[] de tamaño N , la tarea es encontrar la suma máxima posible de los elementos de la array de modo que el elemento pueda elegirse según las siguientes condiciones:
- Para cada índice i , el valor del elemento es arr[i] , luego podemos agregar cualquier elemento de 1 a min(N, arr[i]) en la suma o dejar ese elemento.
- Si ya se agregó algún elemento a la suma, entonces no podemos agregar el mismo elemento nuevamente a la suma.
Ejemplos:
Entrada: arr[] = {1, 2, 2, 4}
Salida: 7
Explicación:
Inicialmente, la suma total es 0.
Suma después de agregar el elemento en el índice 1 a la suma = 1. Elementos agregados a la suma = {1}
Suma después agregando elemento en el índice 2 a la suma = 3. Elementos agregados a la suma = {1, 2}
Ahora, llegando al índice 3, no podemos agregar ningún elemento del (1 al 2) a la suma porque ya hemos agregado los elementos {1 , 2} en la suma. Entonces, deje el elemento en el índice 3.
Luego agregue el elemento en el índice 4 a la suma ya que 4 no se agregó a la suma antes, por lo tanto, la suma máxima que podemos obtener es 3+4=7.Entrada: arr[] ={4, 4, 1, 5}
Salida: 13
Enfoque: este problema se puede resolver usando la técnica Greedy . A continuación se muestran los pasos:
- Ordena los elementos de la array en orden ascendente.
- Mantenga el número máximo posible (digamos maxPossible) que se puede agregar a la suma total.
- Inicialice maxPossible con el elemento máximo de la array y agréguelo a la suma total.
- Recorra la array desde el final hasta el principio y verifique si el valor del elemento dado se ha agregado a la suma total antes o no.
- Si el valor del elemento se ha agregado antes, agregaremos (elemento – 1) a la suma total y si el valor del elemento es menor que maxPossible , agregaremos ese número y cambiaremos maxPossible al valor del elemento.
- Imprima el valor de la suma total después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function that finds the maximum sum
// of the array elements according to
// the given condition
ll findMaxValue(int arr[], int n)
{
// Sort the array
sort(arr, arr + n);
// Take the max value from the array
ll ans = arr[n - 1];
ll maxPossible = arr[n - 1];
// Iterate from the end of the array
for (int i = n - 2; i >= 0; --i) {
if (maxPossible > 0) {
// Check for the number had
// come before or not
if (arr[i] >= maxPossible) {
// Take the value which is
// not occurred already
ans += (maxPossible - 1);
maxPossible = maxPossible - 1;
}
else {
// Change max to new value
maxPossible = arr[i];
ans += maxPossible;
}
}
}
// Return the maximum sum
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 4, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << findMaxValue(arr, n);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that finds the maximum sum
// of the array elements according to
// the given condition
static int findMaxValue(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
// Take the max value from the array
int ans = arr[n - 1];
int maxPossible = arr[n - 1];
// Iterate from the end of the array
for (int i = n - 2; i >= 0; --i)
{
if (maxPossible > 0)
{
// Check for the number had
// come before or not
if (arr[i] >= maxPossible)
{
// Take the value which is
// not occurred already
ans += (maxPossible - 1);
maxPossible = maxPossible - 1;
}
else
{
// Change max to new value
maxPossible = arr[i];
ans += maxPossible;
}
}
}
// Return the maximum sum
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 4, 4, 1, 5 };
int n = arr.length;
// Function Call
System.out.print(findMaxValue(arr, n));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach # Function that finds the maximum sum # of the array elements according to # the given condition def findMaxValue(arr, n): # Sort the array arr.sort() # Take the max value from the array ans = arr[n - 1] maxPossible = arr[n - 1] # Iterate from the end of the array for i in range(n - 2, -1, -1): if (maxPossible > 0): # Check for the number had # come before or not if (arr[i] >= maxPossible): # Take the value which is # not occurred already ans += (maxPossible - 1) maxPossible = maxPossible - 1 else: # Change max to new value maxPossible = arr[i] ans += maxPossible # Return the maximum sum return ans # Driver code if __name__=='__main__': # Given array arr[] arr = [ 4, 4, 1, 5 ] n = len(arr) # Function call print(findMaxValue(arr,n)) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds the maximum sum
// of the array elements according to
// the given condition
static int findMaxValue(int []arr, int n)
{
// Sort the array
Array.Sort(arr);
// Take the max value from the array
int ans = arr[n - 1];
int maxPossible = arr[n - 1];
// Iterate from the end of the array
for (int i = n - 2; i >= 0; --i)
{
if (maxPossible > 0)
{
// Check for the number had
// come before or not
if (arr[i] >= maxPossible)
{
// Take the value which is
// not occurred already
ans += (maxPossible - 1);
maxPossible = maxPossible - 1;
}
else
{
// Change max to new value
maxPossible = arr[i];
ans += maxPossible;
}
}
}
// Return the maximum sum
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 4, 4, 1, 5 };
int n = arr.Length;
// Function Call
Console.Write(findMaxValue(arr, n));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program for the above approach
// Function that finds the maximum sum
// of the array elements according to
// the given condition
function findMaxValue(arr, n)
{
// Sort the array
arr.sort((a, b) => a - b);
// Take the max value from the array
let ans = arr[n - 1];
let maxPossible = arr[n - 1];
// Iterate from the end of the array
for (let i = n - 2; i >= 0; --i) {
if (maxPossible > 0) {
// Check for the number had
// come before or not
if (arr[i] >= maxPossible) {
// Take the value which is
// not occurred already
ans += (maxPossible - 1);
maxPossible = maxPossible - 1;
}
else {
// Change max to new value
maxPossible = arr[i];
ans += maxPossible;
}
}
}
// Return the maximum sum
return ans;
}
// Driver Code
// Given array arr[]
let arr = [ 4, 4, 1, 5 ];
let n = arr.length;
// Function Call
document.write(findMaxValue(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
13
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)