Maximum subsequence sum possible by multiplying each element by its index

0 0 9 minutes read

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(2^N)
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 array
int dp[1005][1005];
 
// Function to find the maximum
// sum of the subsequence formed
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]
            = max(ans1, ans2));
}
 
// Function to calculate maximum sum
// of the subsequence obtained
int 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 Code
int 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 approach
import java.util.*;
class GFG{
 
// Initialize dp array
static int [][]dp = new int[1005][1005];
 
// Function to find the maximum
// sum of the subsequence formed
static 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 obtained
static 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 Code
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
  maximumSum(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach 
 
# Initialize dp array
dp = [[-1 for x in range(1005)]
          for y in range(1005)]
 
# Function to find the maximum
# sum of the subsequence formed
def 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 array
arr = [ -1, 2, -10, 4, -20 ]
 
# Size of the array
N = len(arr)
 
# Function call
maximumSum(arr, N)
 
# This code is contributed by Shivam Singh

C#

// C# program for 
// the above approach
using System;
class GFG{
 
// Initialize dp array
static int [,]dp = new int[1005, 1005];
 
// Function to find the maximum
// sum of the subsequence formed
static 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 obtained
static 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 Code
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
  maximumSum(arr, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for
// the above approach
 
// Let initialize dp array
let dp = new Array(1005);
 
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
    dp[i] = new Array(2);
}
  
// Function to find the maximum
// sum of the subsequence formed
function 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 obtained
function 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:

Time Complexity: O(N²)
Auxiliary Space: O(N²)

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 formed
int 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 array
arr = [-1, 2, -10, 4, -20]
# Size of the array
N = len(arr)
 
# Function call
print(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 formed
function 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 array
let arr = [ -1, 2, -10, 4, -20 ];
 
// Size of the array
let N = arr.length;
 
// Function Call
console.log(maximumSum(arr, N));

Output

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 zambiatek!