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

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

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.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

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.