Maximum Sum Increasing Subsequence
01 · Problem
Given an integer array nums, choose a subsequence (keep elements in their original order, possibly skipping some) whose values are strictly increasing from left to right. Return the largest possible sum of such a subsequence.
A subsequence must contain at least one element, and a single element is always strictly increasing.
02 · Examples
nums = [1,101,2,3,100,4,5]
106
The subsequence [1,2,3,100] sums to 106, which beats [1,101] (102) and [1,2,3,4,5] (15).
nums = [3,4,5,10]
22
The whole array is already strictly increasing, so take all of it: 3 + 4 + 5 + 10 = 22.
nums = [10,5,4,3]
10
The array is decreasing, so every increasing subsequence has one element; the largest is 10.
03 · Constraints
- 011 <= nums.length <= 1000
- 021 <= nums[i] <= 104
- 03The answer fits in a 32-bit signed integer
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.