Maximum Sum Increasing Subsequence

Problem Statement

In the “Maximum Sum Increasing Subsequence” problem we have given an array. Find the sum of the maximum subsequence of the given array, that is the integers in the subsequence are in sorted order.

A subsequence is a part of an array which is a sequence that is derived from another sequence by deleting some elements without changing the order. This can be explained in the below example.

Example

4
18 5 17 23

45

Explanation: In the above example, 45 is the maximum sum. In the above example, there are two increasing subsequences ie, {18, 17} and {5, 17, 23}. But the second subsequence has the maximum sum.

Approach

Given an array of positive numbers. We have to calculate the sum of the maximum sum subsequence of the array such that the subsequence is in increasing_order. 

Example-  [2,5,8,3,4,6]

Then some increasing subsequences are – 

[2,5,8], sum = 15

[2,8], sum = 10

[5,8], sum=13

[2,3,4,6] , sum = 15

[2,5,6] , sum = 13 etc. The maximum sum we get is 15.

The problem can be broken down into simple subproblems, which means it has an optimal substructure.  And the problem also has overlapping subproblems if we draw its recursion tree. Since the problem has optimal substructure and overlapping subproblems, the problem can be solved using dynamic programming. Let a[0,1,……n-1] be an array and dp[i] =maximum sum increasing subsequence ending at index i, such that a[i] is the last element.

Then dp[i] can be written as, 

dp[i] = a[i] + max(L[j]) where  0<j<i and a[j]<a[i]

The ans will be max(dp[i]) where 0<i<n;

Approach

1. We will create a new array dp, where dp[i] =a[i] , where 0<i<n.
2. We will run a outer loop from 0 < i < n.
3. For each i which stores a maximum sum increasing subsequence of a[0,i-1] that ends with i. FInd increasing subsequence with the maximum sum that ends with a[j], where a[j] is less than the current element a[i]
4. Find the maximum in the dp array.

Implementation

C++ Program for Maximum Sum Increasing Subsequence

#include <bits/stdc++.h>
using namespace std;

int max_sum_inc_sub(vector<int> a,int n){
  vector<int> dp(a);
  int ans = 0;
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
        dp[i] = dp[j]+a[i];
      }
    }
    ans = max(ans,dp[i]);
  }
  return ans;
}
int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
  }
  int max_sum = max_sum_inc_sub(a,n);
  cout<<max_sum<<endl;
  return 0;
}

Java Program for Maximum Sum Increasing Subsequence

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_sum_inc_sub(arr,n);
        System.out.println(ans);
  }
  
  public static int max_sum_inc_sub(int[] a,int n){
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
        	dp[i]=a[i];
        }
        int ans = 0;
    for(int i=1;i<n;i++){
      for(int j=0;j<i;j++){
        if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
          dp[i] = dp[j]+a[i];
        }
      }
      ans = Math.max(ans,dp[i]);
    }
    return ans;
    }

}

6
2 5 8 3 4 6

15

Complexity Analysis for Maximum Sum Increasing Subsequence

Time Complexity

O(n*n) where n is the size of the given array. Here we run two nested for loops which leads us to quadratic time complexity.

Space Complexity

O(n) because we use a 1-D array. Here we store values in a linear dp array.