Given an array arr[] consisting of N integers, the task is to find the maximum subsequence sum by multiplying each element of the resultant subsequence by its index(1-based indexing).
Examples:
Input: arr[] = {-1, 2, -10, 4, -20}
Output: 15
Explanation:
For the subsequence {-1, 2, 4}, sum of the given subsequence after performing the given operations = 1*(-1) + 2*2 + 3*4 = 15, which is maximum possible.Input: arr[] = {1, 0, -1, 2}
Output: 7
Explanation:
For the subsequence {1, 0, 2}, sum of the given subsequence after performing the given operations = 1*1 + 2*0 + 3*2 = 7, which is maximum possible.
Naive Approach: The idea is to generate all possible subsequences from the array using recursion and calculate the required sum for each subsequence and print the maximum sum.
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using Dynamic Programming as the problem contains many overlapping subproblems. Below are the steps:
- Initialize an auxiliary matrix dp[][], where dp[i][j] stores the maximum value of the subsequence of length j up to index i.
- Traverse the given array and for each element, there are 2 possibilities:
- Either to include the current element into the subsequence sum and increment the number of elements in subsequence.
- Or exclude the current element from the subsequence and proceed to the next element.
- Therefore, the recurrence relation is given by the following equation:
dp[i][j] = max(a[i] * j + maximumSum(j + 1, i + 1), maximumSum(j, i + 1))
- Keep updating the dp[][] table by using the above recurrence relation for every index and return the maximum sum possible from the entire array.
- Print the maximum value after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Initialize dp arrayint dp[1005][1005];// Function to find the maximum// sum of the subsequence formedint maximumSumUtil(int a[], int index, int count, int n){ // Base Case if (index > n || count > n + 1) { return 0; } // If already calculated // state occurs if (dp[index][count] != -1) return dp[index][count]; // Include the current element int ans1 = maximumSumUtil(a, index + 1, count + 1, n) + a[index] * count; // Exclude the current element int ans2 = maximumSumUtil(a, index + 1, count, n); // Update the maximum ans return (dp[index][count] = max(ans1, ans2));}// Function to calculate maximum sum// of the subsequence obtainedint maximumSum(int arr[], int N){ // Initialise the dp array with -1 memset(dp, -1, sizeof(dp)); // Print the maximum sum possible cout << maximumSumUtil(arr, 0, 1, N - 1);}// Driver Codeint main(){ // Given array int arr[] = { -1, 2, -10, 4, -20 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maximumSum(arr, N); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{// Initialize dp arraystatic int [][]dp = new int[1005][1005];// Function to find the maximum// sum of the subsequence formedstatic int maximumSumUtil(int a[], int index, int count, int n){ // Base Case if (index > n || count > n + 1) { return 0; } // If already calculated // state occurs if (dp[index][count] != -1) return dp[index][count]; // Include the current element int ans1 = maximumSumUtil(a, index + 1, count + 1, n) + a[index] * count; // Exclude the current element int ans2 = maximumSumUtil(a, index + 1, count, n); // Update the maximum ans return (dp[index][count] = Math.max(ans1, ans2));}// Function to calculate maximum sum// of the subsequence obtainedstatic void maximumSum(int arr[], int N){ // Initialise the dp array with -1 for(int i = 0; i < 1005; i++) { for (int j = 0; j < 1005; j++) { dp[i][j] = -1; } } // Print the maximum sum possible System.out.print(maximumSumUtil(arr, 0, 1, N - 1));}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = {-1, 2, -10, 4, -20}; // Size of the array int N = arr.length; // Function Call maximumSum(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Initialize dp arraydp = [[-1 for x in range(1005)] for y in range(1005)]# Function to find the maximum# sum of the subsequence formeddef maximumSumUtil(a, index, count, n): # Base Case if (index > n or count > n + 1): return 0 # If already calculated # state occurs if (dp[index][count] != -1): return dp[index][count] # Include the current element ans1 = (maximumSumUtil(a, index + 1, count + 1, n) + a[index] * count) # Exclude the current element ans2 = maximumSumUtil(a, index + 1, count, n) # Update the maximum ans dp[index][count] = max(ans1, ans2) return dp[index][count]# Function to calculate maximum sum# of the subsequence obtained def maximumSum(arr, N): # Print the maximum sum possible print(maximumSumUtil(arr, 0, 1, N - 1))# Driver Code# Given arrayarr = [ -1, 2, -10, 4, -20 ]# Size of the arrayN = len(arr)# Function callmaximumSum(arr, N)# This code is contributed by Shivam Singh |
C#
// C# program for // the above approachusing System;class GFG{// Initialize dp arraystatic int [,]dp = new int[1005, 1005];// Function to find the maximum// sum of the subsequence formedstatic int maximumSumUtil(int []a, int index, int count, int n){ // Base Case if (index > n || count > n + 1) { return 0; } // If already calculated // state occurs if (dp[index, count] != -1) return dp[index, count]; // Include the current element int ans1 = maximumSumUtil(a, index + 1, count + 1, n) + a[index] * count; // Exclude the current element int ans2 = maximumSumUtil(a, index + 1, count, n); // Update the maximum ans return (dp[index, count] = Math.Max(ans1, ans2));}// Function to calculate maximum sum// of the subsequence obtainedstatic void maximumSum(int []arr, int N){ // Initialise the dp array with -1 for(int i = 0; i < 1005; i++) { for (int j = 0; j < 1005; j++) { dp[i, j] = -1; } } // Print the maximum sum possible Console.Write(maximumSumUtil(arr, 0, 1, N - 1));}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = {-1, 2, -10, 4, -20}; // Size of the array int N = arr.Length; // Function Call maximumSum(arr, N);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for// the above approach// Let initialize dp arraylet dp = new Array(1005);// Loop to create 2D array using 1D arrayfor (var i = 0; i < dp.length; i++) { dp[i] = new Array(2);} // Function to find the maximum// sum of the subsequence formedfunction maximumSumUtil(a, index, count, n){ // Base Case if (index > n || count > n + 1) { return 0; } // If already calculated // state occurs if (dp[index][count] != -1) return dp[index][count]; // Include the current element let ans1 = maximumSumUtil(a, index + 1, count + 1, n) + a[index] * count; // Exclude the current element let ans2 = maximumSumUtil(a, index + 1, count, n); // Update the maximum ans return (dp[index][count] = Math.max(ans1, ans2));} // Function to calculate maximum sum// of the subsequence obtainedfunction maximumSum(arr, N){ // Initialise the dp array with -1 for(let i = 0; i < 1005; i++) { for (let j = 0; j < 1005; j++) { dp[i][j] = -1; } } // Print the maximum sum possible document.write(maximumSumUtil(arr, 0, 1, N - 1));}// Driver code // Given array let arr = [-1, 2, -10, 4, -20]; // Size of the array let N = arr.length; // Function Call maximumSum(arr, N); </script> |
Output:
15
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table DP to store the solution of the subproblems and initialize it with 0.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Take two variables ans1 and ans2 for two previous computations and get the maximum from them and store in dp
- Return the final solution stored in dp[0][1].
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// sum of the subsequence formedint maximumSum(int a[], int n){ // initialize Dp to store computation of subproblems int dp[n+1][n+2]; memset(dp, 0, sizeof(dp)); // Traverse the array in reverse order and fill the dp table for(int i=n-1; i>=0; i--){ for(int j=1; j<=n+1; j++){ // Include the current element int ans1 = dp[i+1][j+1] + a[i]*j; // Exclude the current element int ans2 = dp[i+1][j]; // Update the maximum ans dp[i][j] = max(ans1, ans2); } } // Return the answer return dp[0][1];}int main(){ // Given array int arr[] = { -1, 2, -10, 4, -20 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << maximumSum(arr, N); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;class Main { // Function to find the maximum sum of the subsequence // formed static int maximumSum(int a[], int n) { // initialize Dp to store computation of subproblems int[][] dp = new int[n + 1][n + 2]; for (int[] row : dp) { Arrays.fill(row, 0); } // Traverse the array in reverse order and fill the // dp table for (int i = n - 1; i >= 0; i--) { for (int j = 1; j <= n + 1; j++) { // check if the indices are within bounds if (i + 1 < n && j + 1 < n + 2) { // Include the current element int ans1 = dp[i + 1][j + 1] + a[i] * j; // Exclude the current element int ans2 = dp[i + 1][j]; // Update the maximum ans dp[i][j] = Math.max(ans1, ans2); } } } // Return the answer return dp[0][1]; } public static void main(String[] args) { // Given array int[] arr = { -1, 2, -10, 4, -20 }; // Size of the array int N = arr.length; // Function Call System.out.println(maximumSum(arr, N)); }} |
Python3
def maximumSum(a, n): # initialize dp to store computation of subproblems dp = [[0] * (n+2) for _ in range(n+1)] # Traverse the array in reverse order and fill the dp table for i in range(n-1, -1, -1): for j in range(1, n+2): # check if the indices are within bounds if i+1 < n and j+1 < n+2: # Include the current element ans1 = dp[i+1][j+1] + a[i] * j # Exclude the current element ans2 = dp[i+1][j] # Update the maximum ans dp[i][j] = max(ans1, ans2) # Return the answer return dp[0][1]# Given arrayarr = [-1, 2, -10, 4, -20]# Size of the arrayN = len(arr)# Function callprint(maximumSum(arr, N)) |
C#
using System;class MainClass { // Function to find the maximum sum of the subsequence // formed static int maximumSum(int[] a, int n) { // initialize Dp to store computation of subproblems int[][] dp = new int[n + 1][]; for (int i = 0; i < dp.Length; i++) { dp[i] = new int[n + 2]; for (int j = 0; j < dp[i].Length; j++) { dp[i][j] = 0; } } // Traverse the array in reverse order and fill the // dp table for (int i = n - 1; i >= 0; i--) { for (int j = 1; j <= n + 1; j++) { // check if the indices are within bounds if (i + 1 < n && j + 1 < n + 2) { // Include the current element int ans1 = dp[i + 1][j + 1] + a[i] * j; // Exclude the current element int ans2 = dp[i + 1][j]; // Update the maximum ans dp[i][j] = Math.Max(ans1, ans2); } } } // Return the answer return dp[0][1]; } public static void Main(string[] args) { // Given array int[] arr = { -1, 2, -10, 4, -20 }; // Size of the array int N = arr.Length; // Function Call Console.WriteLine(maximumSum(arr, N)); }} |
Javascript
// JavaScript program for above approach// Function to find the maximum// sum of the subsequence formedfunction maximumSum(a, n){ // initialize Dp to store computation of subproblems let dp = new Array(n+1).fill(0).map(() => new Array(n+2).fill(0)); // Traverse the array in reverse order and fill the dp table for(let i=n-1; i>=0; i--) { for(let j=1; j<=n+1; j++) { // Include the current element let ans1 = dp[i+1][j+1] + a[i]*j; // Exclude the current element let ans2 = dp[i+1][j]; // Update the maximum ans dp[i][j] = Math.max(ans1, ans2); } } // Return the answer return dp[0][1];}// Given arraylet arr = [ -1, 2, -10, 4, -20 ];// Size of the arraylet N = arr.length;// Function Callconsole.log(maximumSum(arr, N)); |
Output
15
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
