Maximum Sum Increasing Subsequence

November 24, 2021

Maximum Sum Increasing Subsequence

The maximum sum incresasing subsequence is a variation of the very famous problem – Longest Increasing subsequence. In this article we provide a C++ solution with explanation of the problem.

Maximum Sum Increasing Subsequence Problem Description

Given an array of n integers, output the maximum sum of an increasing subsequence ie the sequence should be increasing and out of all increasing subsequences output the maximum possible sum.

Input:

First-line contains integer n – the length of the array.
The next line contains n integers.

Output:

Single Integer, the required sum.

Example:

Input:

4
1 3 1 100

Output:

104 {1+ 3 + 100}

Possible subsequences are –

1, 100 with sum = 101
1, 3, 100 with sum = 104
3, 100 with sum = 103
1 with sum = 1
3 with sum = 3
100 with sum = 100

104 is the maximum sum and thus the answer.

Solution Explanation

This problem is a variation of longest increasing subsequence problem.

In LIS we use dp[] array and store the length of increasing susequence ending at i. In this problem instead of length we will store sum of subsequence.

Time Complexity – The time complexity is O(n^2) as we used two nested array to compute the sum.

Space Complexity – The space complexity is O(n) as we use only one auxiliary array to store the result.

Code

#include <bits/stdc++.h>
using namespace std;
int f(int arr[], int n)
{
    int dp[n];
    // Dp array to store msi subsequence ending at i
 
    int ans = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++)
        {
            if (arr[j] <= arr[i]) // as j arr[i] can extend
            {                     // msi subsequence ending at j
                dp[i] = max(dp[i], arr[i] + dp[j]);
            }
        }
        // Checking max sum of all i
        ans = max(ans, dp[i]);
    }
 
    return ans;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    cout << f(arr, n) << endl;
    return 0;
}

Output

3
3 1 100
103