Maximize the Sum of a Subsequence from an Array based on given conditions
Given an array a[] consisting of N integers, the task is to perform the following operations:
- Select a subsequence and for every pth element of the subsequence, calculate the product p * a[i].
- Calculate the sum of the calculated values of p * a[i].
- The subsequence should be selected such that it maximizes the desired sum.
Examples:
Input: N = 3, a[] = {-1, 3, 4}
Output: 17
Explanation:
The subsequence {-1, 3, 4} maximizes the sum = 1(-1) + 2(3) + 3(4) = 17
Input: N = 5, a[] = {-1, -9, 0, 5, -7}
Output: 14
Explanation:
The subsequence {-1, 0, 5} maximizes the sum = 1(-1) + 2(0) + 3(5) = 14
Naive Approach: The simplest approach to solve the problem is to generate all possible subsequences from the array and calculate the sum for each subsequence. Finally, find the maximum sum.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by using Dynamic Programming. Follow the steps below to solve the problem:
- For every element, two possibilities exist, that is, either the element is part of the subsequence or is not.
- Initialize a dp[][] matrix, where dp[i][j] stores the maximum of:
- Sum generated by selecting a[i] as the jth element of the subsequence, that is:
a[i] * j + maximumSum(j + 1, i + 1)
- Sum generated by selecting a[i] as the jth element of the subsequence, that is:
- Sum generated by not selecting a[i] as the jth element of the subsequence, that is:
maximumSum(j, i + 1)
Therefore, the recurrence relation is:
dp[i][j] = max(a[i] * j + maximumSum(j + 1, i + 1), maximumSum(j, i + 1))
- Keep updating the dp[][] table by considering the above conditions for each array element and print the maximum sum possible from the entire array.
Below is the implementation of the above approach:
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
Time Complexity: O(N2)
Auxiliary Space: O(N2)