Maximum Sum Increasing Subsequence — Problem & Solution
Maximum Sum Increasing Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Sum Increasing Subsequence is a medium coding problem on arrays and dynamic programming, asked in Amazon, Microsoft and Morgan Stanley interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of positive integers arr, return the maximum sum of a strictly increasing subsequence of arr.
A subsequence keeps the elements in their original order but may skip any of them. It is strictly increasing if every element is larger than the one before it. A single element on its own is an increasing subsequence.
Example 1
Input: arr = [1,101,2,3,100]
Output: 106
Explanation: 1, 2, 3, 100 sums to 106 — more than the longer-looking 1, 101.
Example 2
Input: arr = [4,1,2,3]
Output: 6
Explanation: 1, 2, 3 sums to 6, beating the single 4.
Example 3
Input: arr = [5,5,5]
Output: 5
Explanation: Equal values cannot follow each other in a strictly increasing subsequence.
Constraints
1 <= arr.length <= 10001 <= arr[i] <= 10^5
Hints for Maximum Sum Increasing Subsequence
Hint 1
This is the longest increasing subsequence problem with sums in place of lengths — the longest one need not have the largest sum.
Hint 2
Let
best[i]be the largest sum of an increasing subsequence that ends at indexi.Hint 3
best[i] = arr[i] + max(best[j])overj < iwitharr[j] < arr[i](or justarr[i]if there is none). The answer is the largestbest[i].
How to solve Maximum Sum Increasing Subsequence
Fix the last element of the subsequence. Whatever comes before it is itself an increasing subsequence ending at some smaller earlier element, and it should be the heaviest such one. That is the LIS recurrence with sums instead of counts.
Approach
- Initialise
best[i] = arr[i]for everyi. - For each
iand eachj < iwitharr[j] < arr[i]:best[i] = max(best[i], best[j] + arr[i]). - Return the maximum value in
best.
Why it works
An increasing subsequence ending at i is either arr[i] alone or an increasing subsequence ending at some j < i with arr[j] < arr[i], extended by arr[i]. Its sum is maximised by taking the heaviest such prefix, best[j], so the recurrence is exact; every subsequence ends somewhere, so the maximum over all i is the answer.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- Returning
best[n - 1]instead of the maximum over all indices — the best subsequence need not end at the last element. - Using
<=lets equal values chain, but the subsequence must be strictly increasing. - The answer is at most
1000 * 10^5 = 10^8, comfortably inside 32 bits.
Reference solution
Python
from typing import List
def maxSumIS(arr: List[int]) -> int:
best = arr[:]
for i in range(len(arr)):
ai = arr[i]
for j in range(i):
if arr[j] < ai and best[j] + ai > best[i]:
best[i] = best[j] + ai
return max(best)Java
public static int maxSumIS(int[] arr) {
int n = arr.length;
int[] best = arr.clone();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) best[i] = Math.max(best[i], best[j] + arr[i]);
}
ans = Math.max(ans, best[i]);
}
return ans;
}C++
int maxSumIS(vector<int>& arr) {
int n = arr.size();
vector<int> best(arr);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) best[i] = max(best[i], best[j] + arr[i]);
}
ans = max(ans, best[i]);
}
return ans;
}JavaScript
var maxSumIS = function(arr) {
var best = arr.slice();
var ans = 0;
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < i; j++) {
if (arr[j] < arr[i] && best[j] + arr[i] > best[i]) best[i] = best[j] + arr[i];
}
if (best[i] > ans) ans = best[i];
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming