Maximum Sum Increasing Subsequence
Find the largest possible sum of a strictly increasing subsequence of an array.
- 1 <= n <= 10³
- 1 <= nums[i] <= 10⁵
- The subsequence must be strictly increasing
Intuition
Maximum sum increasing subsequence asks for the largest achievable sum of a strictly increasing subsequence. It looks like Longest Increasing Subsequence with a different objective, and the shape of the DP is indeed the same — but the answers genuinely differ.
Optimising sum instead of length changes which chain wins. [1, 2, 3] has length 3 and sum 6; [100] has length 1 and sum 100. The longest chain is not the heaviest one, so an LIS solution cannot simply be relabelled.
The state that works is the same as LIS, though, and the reason is worth understanding. Let dp[i] be the best sum of an increasing subsequence ending exactly at index i. Anchoring at an index is what makes the recurrence well-defined: any chain ending at i must arrive from some earlier index j with a smaller value, and that chain's best sum is already computed.
- dp[i] = nums[i] + max(dp[j]) over all j < i with nums[j] < nums[i], or just nums[i] if no such j exists.
Initialising every dp[i] to nums[i] handles that fallback — a single element is always a valid subsequence.
One easy mistake at the end: the heaviest chain can end anywhere, so the answer is max(dp) rather than dp[n−1]. Returning the last cell works only when the array happens to end on the best chain.
Note also that negative values are handled correctly by this formulation, since a chain of one element is always allowed.
Longest-increasing-subsequence with the objective swapped from count to sum. The O(n²) shape is identical — for each i, scan every earlier j that could precede it — but the patience-sorting O(n log n) trick does not transfer, because a smaller tail no longer implies a better state when sums are involved.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n²) time and O(n) space.
See why LIS does not transfer directly
The longest increasing chain is not always the heaviest — [1, 2, 3] sums to 6 while [100] sums to 100. The DP shape carries over but the answers differ, so an LIS solution cannot simply be reused.
Anchor the state at an index
dp[i] is the maximum sum of an increasing subsequence ending exactly at i. Anchoring is what makes the recurrence work: every such chain arrives from a specific earlier index whose answer is already known.
Initialise each cell to its own value
Set dp[i] = nums[i] before the inner loop, since a single element is always a valid increasing subsequence. This also handles negative values correctly — a chain of one is permitted even when it is negative.
Extend from smaller predecessors
For each j < i with nums[j] < nums[i], take dp[i] = max(dp[i], dp[j] + nums[i]). The comparison is strict, since the subsequence must strictly increase — using <= would admit equal values.
Return the maximum, not the last cell
The best chain may end anywhere in the array, so the answer is max(dp). Returning dp[n-1] is the classic error and happens to be right only when the array ends on the optimal chain.
Cost of the quadratic DP
The nested loops give O(n²) time and O(n) space. Unlike LIS, this problem has no straightforward O(n log n) improvement — the patience-sorting trick relies on lengths, and sums do not order the same way.
Solution & live demo
Common pitfalls
Initialising the table to zero
dp = [0] * len(nums)
dp = nums[:]
Every element is a valid one-element subsequence worth its own value. Starting at 0 loses that base case, and an array of negatives would report 0 — a subsequence that doesn't exist.
Extending without checking the increasing condition
if dp[j] + nums[i] > dp[i]:
if nums[j] < nums[i] and dp[j] + nums[i] > dp[i]:
Without the value comparison this maximises over any subsequence, not an increasing one — it just sums the positives. The ordering constraint is what makes the problem non-trivial.
Returning the last cell
return dp[-1]
return max(dp)
dp[i] is the best sum for a subsequence ending at i, and the optimal one rarely ends at the final element. The answer is the maximum across all endings.
Edge cases
No element has a smaller predecessor, so dp[i] = nums[i] and the answer is the single largest value.
The comparison is strict (<), so equal values cannot extend each other.
dp = [nums[0]] and the answer is that element.