Maximum Sum Increasing Subsequence

Problem Statement

An array of positive integers of size n is given. write a program to find the maximum sum increasing subsequence in the given array. The maximum sum increasing subsequence is a subsequence of an integer array where the sum is maximum and all of the elements are sorted in non decreasing order.

Example

Input-1

Output-1

Explanation

Here, we have given an array of integers 1 5 2 3 9 5 and the output should be $1 + 2 + 3 + 9 = 15$ because there are two subsequences exists that has a maximum sum of 15 i.e 1 5 9 and 1 2 3 9, they are sorted as well in increasing order.

Output-2

Explanation

Here, we have given an array of integers 1 8 3 12 2 10 4 14 2 6 6 13 2 10 and the output should be $1 + 8 + 12 + 14 = 35$ because there is one subsequence exists which has a maximum sum of 35 i.e 1 8 12 14, which is also sorted in increasing order.

Constraints

Algorithm 1 - Naive Approach and algo-1: Using Recursion

Intuition

Since this problem is a variation of the standard Longest Increasing Subsequence problem, hence we can use recursion to solve this problem. For each element in the given array, there are two cases:

• If the current element is greater than the previous element, include it.
• Else exclude the current element and use recursion for the remaining elements in the array.

Algorithm

1. Create a function that takes an arr[] array, a variable i for indexing, a prev variable to keep track of previous elements, and a sum variable for calculating the maximum sum.
2. The base case here is when the arr[] is empty.
3. Check for two cases:
   • Call the recursive function without the current element.
   • If the element is greater than the previous element, call the recursive function for the current element.
4. Finally, return the maximum sum of the above two cases.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(nlogn). Since we are going exponentially(not constant) not linearly (constant change) i.e in each iteration there are two cases to find maximum sum increasing subsequence, where n is the size of the given array.

Space Complexity

The space complexity is O(n). Since recursion takes more space in the call stack to find maximum sum increasing subsequence.

Algorithm 2 - Optimal Approach using DP and algo-2

Intuition

The previous approach can be optimized by doing some slight changes in the Dynamic Programming approach to the Longest Increasing Subsequence problem. i.e replace the sum in place of the length of increasing subsequence.

We can also solve the problem in a bottom-up approach. If we draw the recursion tree for the above approach then we can easily see that there are some overlapping subproblems in the picture below, where substructure properties can be used easily.

Algorithm

1. arr[2] > arr[1] {MSIS[2] = max(MSIS [2], MSIS[1]+1 = 2}
2. arr[3] < arr[1] {No change}
3. arr[3] < arr[2] {No change}
4. arr[4] > arr[1] {MSIS[4] = max(MSIS [4], MSIS[1]+1 = 2}
5. arr[4] > arr[2] {MSIS[4] = max(MSIS [4], MSIS[2]+1 = 3}
6. arr[4] > arr[3] {MSIS[4] = max(MSIS [4], MSIS[3]+1 = 3}

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(n^2^). Since we are using two nested for loops and traversing the array n^2^ times in to find the maximum sum increasing subsequence, where n is the size of the given array.

Space Complexity

The space complexity is O(n). Since we are using an extra array to store MSIS values at each index in the Program to find maximum sum increasing subsequence.