Printing Maximum Sum Increasing Subsequence

The Maximum Sum Increasing Subsequence problem is to find the maximum sum subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Examples: 

Input:  [1, 101, 2, 3, 100, 4, 5]
Output: [1, 2, 3, 100]

Input:  [3, 4, 5, 10]
Output: [3, 4, 5, 10]

Input:  [10, 5, 4, 3]
Output: [10]

Input:  [3, 2, 6, 4, 5, 1]
Output: [3, 4, 5]

In previous post, we have discussed the Maximum Sum Increasing Subsequence problem. However, the post only covered code related to finding maximum sum of increasing subsequence, but not to the construction of subsequence. In this post, we will discuss how to construct Maximum Sum Increasing Subsequence itself.

Let arr[0..n-1] be the input array. We define vector L such that L[i] is itself is a vector that stores Maximum Sum Increasing Subsequence of arr[0..i] that ends with arr[i]. Therefore for index i, L[i] can be recursively written as 

L[0] = {arr[0]}
L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i]
     = arr[i], if there is no j such that arr[j] < arr[i]

For example, for array [3, 2, 6, 4, 5, 1], 

L[0]: 3
L[1]: 2
L[2]: 3 6
L[3]: 3 4
L[4]: 3 4 5
L[5]: 1

Below is the implementation of the above idea – 

3 4 5

 We can optimize the above DP solution by removing findSum() function. Instead, we can maintain another vector/array to store sum of maximum sum increasing subsequence that ends with arr[i]. The implementation can be seen here.

Time complexity of above Dynamic Programming solution is O(n²). 
Auxiliary space used by the program is O(n²).

Approach 2: (Using Dynamic Programming Using O(N) space

The above approach covered how to construct a Maximum Sum Increasing Subsequence in O(N²) time and O(N²) space. In this approach, we will optimize the Space complexity and construct the Maximum Sum Increasing Subsequence in O(N²)  time and O(N) space.

• Let arr[0..n-1] be the input array.
• We define a vector of pairs L such that L[i] first stores the Maximum Sum Increasing Subsequence of arr[0..i] that ends with arr[i] and L[i].second stores the index of the previous element used for generating the sum.
• As the first element does not have any previous element hence its index would be -1 in L[0].

For example, 

array = [3, 2, 6, 4, 5, 1]

L[0]: {3, -1}
L[1]: {2,  1}
L[2]: {9,  0}
L[3]: {7, 0}
L[4]: {12, 3}
L[5]: {1, 5}

As we can see above, the value of the Maximum Sum Increasing Subsequence is 12. To construct the actual Subsequence we will use the index stored in L[i].second. The steps to construct the Subsequence is shown below: 

• In a vector result, store the value of the element where the Maximum Sum Increasing Subsequence was found (i.e at currIndex = 4). So in the result vector, we will add arr[currIndex].
• Update the currIndex to L[currIndex].second and repeat step 1 until currIndex is not -1 or it does not changes (i.e currIndex == previousIndex).
• Display the elements of the result vector in reverse order.

Below is the implementation of the above idea : 

1 2 3 100

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

This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.