Maximizar la suma de una subsecuencia de una array en función de las condiciones dadas

Dada una array a[] que consta de N enteros, la tarea es realizar las siguientes operaciones: 
 

• Seleccione una subsecuencia y para cada p ^-ésimo elemento de la subsecuencia, calcule el producto p * a[i] .
• Calcule la suma de los valores calculados de p * a[i] .
• La subsecuencia debe seleccionarse de manera que maximice la suma deseada.

Ejemplos:

Entrada: N = 3, a[] = {-1, 3, 4} 
Salida: 17 
Explicación: 
La subsecuencia {-1, 3, 4} maximiza la suma = 1(-1) + 2(3) + 3( 4) = 17
Entrada: N = 5, a[] = {-1, -9, 0, 5, -7} 
Salida: 14 
Explicación: 
La subsecuencia {-1, 0, 5} maximiza la suma = 1(- 1) + 2(0) + 3(5) = 14

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subsecuencias posibles a partir de la array y calcular la suma de cada subsecuencia. Finalmente, encuentre la suma máxima. 
Complejidad temporal: O(N ³ ) 
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la programación dinámica . Siga los pasos a continuación para resolver el problema:

• Para todo elemento existen dos posibilidades, es decir, o el elemento es parte de la subsecuencia o no lo es.
• Inicialice una array dp[][] , donde dp[i][j] almacena el máximo de: 
  • Suma generada al seleccionar a[i] como el j ^-ésimo elemento de la subsecuencia, es decir:
    

    a[i] * j + sumamáxima(j + 1, i + 1)

• Suma generada al no seleccionar a[i] como el j ^-ésimo elemento de la subsecuencia, es decir:
  

  sumamáxima(j, i + 1)

  Por lo tanto, la relación de recurrencia es:

  dp[i][j] = max(a[i] * j + sumamáxima(j + 1, i + 1), sumamáxima(j, i + 1))

• Siga actualizando la tabla dp[][] considerando las condiciones anteriores para cada elemento de la array e imprima la suma máxima posible de toda la array.

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
  
// Function to select the array elements to
// maximize the sum of the selected elements
int maximumSum(int a[], int count, 
               int index, int n, 
               int dp[N][N])
{
    // If the entire array
    // is solved
    if (index == n)
        return 0;
  
    // Memoized subproblem
    if (dp[index][count] != -1)
        return dp[index][count];
  
    // Calculate sum considering the
    // current element in the subsequence
    int take_element = a[index] * count + 
                         maximumSum(a, count + 1, 
                                  index + 1, n, dp);
  
    // Calculate sum without considering the
    // current element in the subsequence
    int dont_take = maximumSum(a, count, 
                               index + 1, n, dp);
  
    // Update the maximum of the above sums
    // in the dp[][] table
    return dp[index][count] = max(take_element, 
                                  dont_take);
}
  
// Driver Code
int main()
{
    int n = 5;
    int a[] = { -1, -9, 0, 5, -7 };
  
    // Initialize the dp array
    int dp[N][N];
    memset(dp, -1, sizeof(dp));
  
    cout << (maximumSum(a, 1, 0, n, dp));
}
  
// This code is contributed by Rajput-Ji

// Java program to implement
// the above approach
import java.util.*;
  
public class GFG {
  
    // Function to select the array elements to
    // maximize the sum of the selected elements
    public static int maximumSum(int[] a, int count,
                                 int index, int n,
                                 int[][] dp)
    {
        // If the entire array
        // is solved
        if (index == n)
            return 0;
  
        // Memoized subproblem
        if (dp[index][count] != -1)
            return dp[index][count];
  
        // Calculate sum considering the
        // current element in the subsequence
        int take_element
            = a[index] * count
              + maximumSum(a, count + 1,
                           index + 1, n, dp);
  
        // Calculate sum without considering the
        // current element in the subsequence
        int dont_take
            = maximumSum(a, count, index + 1, n, dp);
  
        // Update the maximum of the above sums
        // in the dp[][] table
        return dp[index][count]
            = Math.max(take_element, dont_take);
    }
  
    // Driver Code
    public static void main(String args[])
    {
        int n = 5;
        int a[] = { -1, -9, 0, 5, -7 };
  
        // Initialize the dp array
        int dp[][] = new int[n + 1][n + 1];
        for (int i[] : dp)
            Arrays.fill(i, -1);
  
        System.out.println(maximumSum(a, 1, 0, n, dp));
    }
}

# Python3 program to implement
# the above approach
  
# Function to select the array elements to
# maximize the sum of the selected elements
def maximumSum(a, count, index, n, dp):
  
    # If the entire array
    # is solved
    if(index == n):
        return 0
  
    # Memoized subproblem
    if(dp[index][count] != -1):
        return dp[index][count]
  
    # Calculate sum considering the
    # current element in the subsequence
    take_element = (a[index] * count + 
                 maximumSum(a, count + 1,
                               index + 1, 
                               n, dp))
  
    # Calculate sum without considering the
    # current element in the subsequence
    dont_take = maximumSum(a, count, 
                           index + 1, n, dp)
  
    # Update the maximum of the above sums
    # in the dp[][] table
    dp[index][count] = max(take_element,
                           dont_take)
                             
    return dp[index][count]
  
# Driver Code
n = 5
a = [ -1, -9, 0, 5, -7 ]
  
# Initialize the dp array
dp = [[-1 for x in range(n + 1)]
          for y in range(n + 1)]
  
# Function call
print(maximumSum(a, 1, 0, n, dp))
  
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
  
class GFG{
  
// Function to select the array elements to
// maximize the sum of the selected elements
public static int maximumSum(int[] a, int count,
                             int index, int n,
                             int[,] dp)
{
      
    // If the entire array
    // is solved
    if (index == n)
        return 0;
  
    // Memoized subproblem
    if (dp[index, count] != -1)
        return dp[index, count];
  
    // Calculate sum considering the
    // current element in the subsequence
    int take_element = a[index] * count + 
                       maximumSum(a, count + 1,
                                     index + 1,
                                     n, dp);
  
    // Calculate sum without considering the
    // current element in the subsequence
    int dont_take = maximumSum(a, count, 
                               index + 1, n, dp);
  
    // Update the maximum of the above sums
    // in the [,]dp table
    return dp[index, count] = Math.Max(take_element, 
                                       dont_take);
}
  
// Driver Code
public static void Main(String []args)
{
    int n = 5;
    int []a = { -1, -9, 0, 5, -7 };
  
    // Initialize the dp array
    int [,]dp = new int[n + 1, n + 1];
    for(int i = 0; i < n + 1; i++)
    {
        for(int j = 0; j < n + 1; j++)
        {
            dp[i, j] = -1;
        }
    }
    Console.WriteLine(maximumSum(a, 1, 0, n, dp));
}
}
  
// This code is contributed by PrinciRaj1992

<script>
  
// JavaScript program to implement
// the above approach
var N = 6;
  
// Function to select the array elements to
// maximize the sum of the selected elements
function maximumSum(a, count, index, n, dp)
{
    // If the entire array
    // is solved
    if (index == n)
        return 0;
  
    // Memoized subproblem
    if (dp[index][count] != -1)
        return dp[index][count];
  
    // Calculate sum considering the
    // current element in the subsequence
    var take_element = a[index] * count + 
                         maximumSum(a, count + 1, 
                                  index + 1, n, dp);
  
    // Calculate sum without considering the
    // current element in the subsequence
    var dont_take = maximumSum(a, count, 
                               index + 1, n, dp);
  
    // Update the maximum of the above sums
    // in the dp[][] table
    return dp[index][count] = Math.max(take_element, 
                                  dont_take);
}
  
// Driver Code
var n = 5;
var a = [ -1, -9, 0, 5, -7];
// Initialize the dp array
var dp = Array.from(Array(N), ()=>Array(N).fill(-1));
document.write(maximumSum(a, 1, 0, n, dp));
  
  
</script>

14

Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar: O(N ² )