In this problem (Maximum Sum Increasing Subsequence), we are given an array and we need to find out the maximum sum increasing subsequence from that array. This can be solved using Dynamic Programming.

Let us first understand what do we mean by Increasing Subsequence.

• A subsequence is a sequence in an array that occurs in the same relative order.

For example, if the array is [2,5,8,3,4,6] , then
[2,8,3] , [3,4,6] , [5,3,6]...etc are some subsequences of the array.

• In an Increasing subsequence, the elements will occur in the same relative order, and that order must be increasing as well.

For the previous example, [2,3,4] will be an increasing subsequence.

• What is Maximum Sum Increasing order?

Given any array, the maximum sum that we can find from all the increasing subsequences of that array will be the Maximum sum increasing order.

For example:
Let arr = [3, 2, 6, 4, 5, 1]

The increasing subsequences of arr would be [3, 6] , [3, 4, 5] , [3, 5] , [2, 4, 5] etc..

Out of all these increasing subsequences, the largest sum would be found from [3, 4, 5] where 3+4+5 = 12.

Hence, [3, 4, 5] is the maximum sum increasing subsequence, and that would be our answer.

Approach -

We will be using Dynamic Programming to tackle this problem. The following approach will be used -

1. We have our given array arr[] with length n.
2. We will create n vectors within a vector L i.e L will be a 2D vector of size n..
3. We will traverse the array in a manner such that we can store all the increasing subsequences of all elements from the array in the 2D vector.
4. From all the increasing subsequences, we will find out the subsequence with the maximum sum and print that subsequence as our result.

Time Complexity : O(n^2)
Space Complexity : O(n^2)

Code -

The following is the solution of the given problem in C++:

/* Dynamic Programming solution to construct
   Maximum Sum Increasing Subsequence */
#include <iostream>
#include <vector>
using namespace std;
 
// Utility function to calculate sum of all
// vector elements
int findSum(vector<int> arr)
{
    int sum = 0;
    for (int i : arr)
        sum += i;
    return sum;
}
 
// Function to construct Maximum Sum Increasing
// Subsequence
void printMaxSumIS(int arr[], int n)
{
    // L[i] - The Maximum Sum Increasing
    // Subsequence that ends with arr[i]
    vector<vector<int> > L(n);
 
    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);
 
    // start from index 1
    for (int i = 1; i < n; i++) {
        // for every j less than i
        for (int j = 0; j < i; j++) {
            /* L[i] = {MaxSum(L[j])} + arr[i]
            where j < i and arr[j] < arr[i] */
            if ((arr[i] > arr[j])
                && (findSum(L[i]) < findSum(L[j])))
                L[i] = L[j];
        }
 
        // L[i] ends with arr[i]
        L[i].push_back(arr[i]);
 
        // L[i] now stores Maximum Sum Increasing
        // Subsequence of arr[0..i] that ends with
        // arr[i]
    }
 
    vector<int> res = L[0];
 
    // find max
    for (vector<int> x : L)
        if (findSum(x) > findSum(res))
            res = x;
 
    // max will contain result
    for (int i : res)
        cout << i << " ";
    cout << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 101, 3, 2, 100, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // construct and print Max Sum IS of arr
    cout<<"The increasing subsequence with the maximum sum is : ";
    printMaxSumIS(arr, n);
 
    return 0;
}

Output -

The increasing subsequence with the maximum sum is : 1 3 100

Workflow -

Let's understand the workflow of the given example:
arr[] = [1, 101, 3, 2, 100, 4, 5]

Intially, we will set L[0] = 1 , as that is the first element in the array.

In this problem, we will traverse through the array such that we visit all elements till arr[i]. Hence, we will need 2 nested for loops, such that the outer for loop (i) traverses through all n elements and the inner for loop (j) traverses till i.

We will follow the conditions in the if statement to store the proper increasing subsequence of an element.

• For i=1 :
  j=0 and L[1] = [1, 101] i.e. the increasing subsequence till arr[i].

• For i=2:
  j=0,1 . L[2] = [1, 3].

• For i=3:
  j=0,1,2 . L[3] = [1, 2].

• For i=4:
  j=0,1,2,3 . L[4] = [1, 3, 100].

• For i=5:
  j=0,1,2,3,4 . L[5] = [1, 3, 4].

• For i=6:
  j=0,1,2,3,4,5 . L[6] = [1, 3, 4, 5].

Hence, out of all these subsequences, we can see that L[4] has the maximum sum i.e 1+3+100 = 104.
Hence, our result is 1 3 100

Complexity

• Time complexity : O(n^2) , since for each element arr[i], we visit all the elements till i.
• Space complexity : O(n^2) , as we use a 2D vector to store the increasing subsequences of all elements.