Encuentre la suma máxima posible para las condiciones dadas

Dada una array arr[] de tamaño N, la tarea es encontrar la suma máxima posible de la array siguiendo las condiciones dadas: 

• En cada paso, solo se puede usar un elemento para aumentar la suma.
• Si se selecciona algún elemento K de la array, los números restantes de la array se reducen en uno.
• Los elementos de la array no se pueden reducir más allá de 0.

Ejemplos:  

Entrada: arr = {6, 6, 6} 
Salida: 15 
Explicación: 
Inicialmente, la suma total es 0. Dado que todos los elementos son iguales, se elige cualquier elemento. 
Suma después de elegir los primeros seis = 6. Elementos restantes = {5, 5}. 
Suma después de elegir los cinco = 11. Elementos restantes = {4}. 
Finalmente, se elige cuatro haciendo la suma máxima 15. 

Entrada: arr = {0, 1, 0} 
Salida: 1 
Explicación: 
Inicialmente, la suma total es 0. Solo hay un número que se puede elegir en la array porque el resto de los elementos son 0. 
Por lo tanto, la suma máxima = 1. 
 

Enfoque: dado que el valor de todos los demás elementos se reduce en 1, claramente obtenemos la suma máxima si elegimos el elemento máximo en cada iteración. Por lo tanto, para hacer esto, se utiliza la clasificación . 

• La idea es ordenar los elementos de la array en orden descendente.
• Ahora, dado que podemos elegir el valor máximo en cada iteración, calculamos el valor del elemento K en algún índice ‘i’ como (K – i) .
• Si en cualquier índice el valor del elemento se vuelve 0, entonces todos los elementos más allá de ese índice serán 0.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find the maximum
// possible Sum for the given conditions
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// possible sum for the
// given conditions
int maxProfit(int arr[], int n)
{
     
    // Sorting the array
    sort(arr, arr + n, greater<int>());
 
    // Variable to store the answer
    int ans = 0;
 
    // Iterating through the array
    for(int i = 0; i < n; i++)
    {
        
       // If the value is greater than 0
       if ((arr[i] - (1 * i)) > 0)
           ans += (arr[i] - (1 * i));
        
       // If the value becomes 0
       // then break the loop because
       // all the weights after this
       // index will be 0
       if ((arr[i] - (1 * i)) == 0)
           break;
    }
     
    // Print profit
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = {6, 6, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
     
    cout << maxProfit(arr, n);
    return 0;
}
 
// This code is contributed by ankitkumar34

// Java program to find the maximum
// possible Sum for the given conditions
import java.util.Arrays;
import java.util.Collections;
 
public class GFG{
 
    // Function to find the maximum
    // possible sum for the
    // given conditions
    static int maxProfit(Integer [] arr)
    {
         
        // Sorting the array
        Arrays.sort(arr, Collections.reverseOrder());
     
        // Variable to store the answer
        int ans = 0;
     
        // Iterating through the array
        for(int i = 0; i < arr.length; i++)
        {
     
           // If the value is greater than 0
           if ((arr[i] - (1 * i)) > 0)
               ans += (arr[i] - (1 * i));
     
           // If the value becomes 0
           // then break the loop because
           // all the weights after this
           // index will be 0
           if ((arr[i] - (1 * i)) == 0)
               break;
        }
         
        // Print profit
        return ans;
    }
     
// Driver code
public static void main(String[] args)
{
    Integer arr[] = { 6, 6, 6 };
    System.out.println(maxProfit(arr));
}
}
 
// This code is contributed by AnkitRai01

# Python3 program to find the maximum
# possible Sum for the given conditions
 
# Function to find the maximum
# possible sum for the
# given conditions
def maxProfit(arr):
     
    # Sorting the array
    arr.sort(reverse = True)
 
    # Variable to store the answer
    ans = 0
 
    # Iterating through the array
    for i in range(len(arr)):
 
        # If the value is greater than 0
        if (arr[i]-(1 * i))>0:
            ans+=(arr[i]-(1 * i))
 
        # If the value becomes 0
        # then break the loop because
        # all the weights after this
        # index will be 0
        if (arr[i]-(1 * i))== 0:
            break
 
    # print profit
    return ans   
 
# Driver code
if __name__ == "__main__":
  
    arr = [6, 6, 6]
 
    print(maxProfit(arr))
  

// C# program to find the maximum
// possible Sum for the given conditions
using System;
 
class GFG{
 
// Function to find the maximum
// possible sum for the
// given conditions
static int maxProfit(int[] arr)
{
         
    // Sorting the array
    Array.Sort(arr);
    Array.Reverse(arr);
     
    // Variable to store the answer
    int ans = 0;
     
    // Iterating through the array
    for(int i = 0; i < arr.Length; i++)
    {
        
       // If the value is greater than 0
       if ((arr[i] - (1 * i)) > 0)
           ans += (arr[i] - (1 * i));
        
       // If the value becomes 0
       // then break the loop because
       // all the weights after this
       // index will be 0
       if ((arr[i] - (1 * i)) == 0)
           break;
    }
         
    // Print profit
    return ans;
}
     
// Driver code
static public void Main ()
{
    int[] arr = { 6, 6, 6 };
     
    Console.Write(maxProfit(arr));
}
}
 
// This code is contributed by Shubhamsingh10

<script>
 
// Javascript program to find the maximum
// possible Sum for the given conditions
 
// Function to find the maximum
// possible sum for the
// given conditions
function maxProfit(arr)
{
     
    // Sorting the array
    arr.sort();
    arr.reverse();
 
    // Variable to store the answer
    let ans = 0;
 
    // Iterating through the array
    for(let i = 0; i < arr.length; i++)
    {
         
        // If the value is greater than 0
        if ((arr[i] - (1 * i)) > 0)
            ans += (arr[i] - (1 * i));
         
        // If the value becomes 0
        // then break the loop because
        // all the weights after this
        // index will be 0
        if ((arr[i] - (1 * i)) == 0)
            break;
    }
 
    // Print profit
    return ans;
}
 
// Driver code
let arr = [ 6, 6, 6 ];
   
document.write(maxProfit(arr));
 
// This code is contributed by divyesh072019
 
</script>

15

Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(1)