Home » Interview coding problems/challenges

Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence: Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.
Submitted by Divyansh Jaipuriyar, on August 31, 2020

Problem statement

Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.

Problem description

Given problem wants you to find the sum of increasing subsequence such that they provide maximum value, this is an application of famous problem of Longest increasing subsequence problem, but here you are required to find the sum not the length so you are required to implement some logic with the help of LIS approach so that it return maximum sum.

Input

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N (the size of array). The second line of each test case contains array elements.

Output

For each test case print the required answer in new line.

Examples

Input:
T=1
N=5
[9,18,2,4,10]

Output:
27, {9,18} forms the Maximum sum increasing subsequence.

Input:
T=1
N=3
[1,2,3]

Output:
6, {1,2,3} forms the maximum sum increasing subsequence.

Solution Approach

This problem is a variation of LIS i.e. longest increasing subsequence problem, we will use recursion approach first to solve the problem:

We have following option with us for each element of the array.

1. Either we can include the given array element if it is greater than the previous element in the increasing subsequence function.
2. We can exclude the current array element and recursively solve for the remaining items.

We pick the maximum value obtained from the above two options in our final answer.
Here we are using the solve function to calculate the maximum sum increasing subsequences.

arr[]=is the input array.

The index i is the index, n is the size of the array, prev is the previous sum and sum is the total maximum sum increasing subsequences that we got.

The recursive function will terminate when the index reaches the end of the array if we start to solve from left and if we start from right then the base condition will be if the index is <0.

Time complexity for the above approach in the worst case is exponential

Space complexity for the above approach in the worst case is: O(1)

Dynamic Programming Approach:

In this approach we will use the same logic as Longest increasing subsequence problem, we will create an array sum[] as the same size as of the given array arr[], we will store the value sum[i] as the maximum sum of an increasing subsequence of subarray arr[0...i] that ends with arr[i].

To calculate the sum[i] we will check the maximum sum increasing subsequence of all the smaller values of i that had already been calculated and then we pick the maximum of them.

Time complexity for the above approach in the worst case is : O(n*n)
Space complexity for the above approach in the worst case is: O(n)

C++ Implementation (Recursion approach):

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

typedef long long ll;

//declare function solve.
ll solve(ll arr[], ll index, ll n, ll previous, ll sum)
{
    //base condition if we
    //reached ahead of last element.
    if (index == n)
        return sum;

    //if we are not including current
    //element.
    ll s1 = solve(arr, index + 1, n, previous, sum);

    //if we are including current element.
    ll s2 = sum; //check condition.
    if (arr[index] > previous)
        s2 = solve(arr, index + 1, n, arr[index], sum + arr[index]);

    //return maximum value
    //from two option.
    return max(s1, s2);
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        cout << "Maximum sum increasing subsequence: ";
        cout << solve(arr, 0, n, INT_MIN, 0) << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter array elements: 1 2 3 4 5
Maximum sum increasing subsequence: 15
Enter size of array: 3
Enter array elements: 10 9 20
Maximum sum increasing subsequence: 30
Enter size of array: 4
Enter array elements: 2 5 1 0 5
Maximum sum increasing subsequence: 7

C++ Implementation (Dynamic Programming):

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

typedef long long ll;

//solve function to calculate
//maximum sum increasing subsequence.
ll solve(ll arr[], ll n)
{
    //initialize sum array with same
    //size as that of given array.
    ll sum[n];

    //initialize each element of sum
    //with same as arr[i].
    for (ll i = 0; i < n; i++)
        sum[i] = arr[i];

    //start iterating from second
    //element till last element.
    for (ll i = 1; i < n; i++) {

        //compare all smaller elements
        //than current element.
        for (ll j = 0; j < i; j++) {

            //check for LIS condition.
            if (arr[i] > arr[j] and sum[i] < sum[j] + arr[i])
                sum[i] = sum[j] + arr[i];
        }
    }
 
    //find maximum value by iterating.
    ll ans = *max_element(sum, sum + n);
 
    //return ans.
    return ans;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;
    
        ll arr[n];
    
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
    
        cout << "Maximum sum increasing subsequence: ";
        cout << solve(arr, n) << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 10 9 8 7 6  
Maximum sum increasing subsequence: 10
Enter size of array: 3
Enter elements: 1 2 3
Maximum sum increasing subsequence: 6
Enter size of array: 5
Enter elements: 9 18 2 4 10
Maximum sum increasing subsequence: 27