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 3 )
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 seleccionar a[i] como el j -ésimo elemento de la subsecuencia, es decir:
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA