Maximum Sum Increasing Subsequence
Find the largest possible sum of a strictly increasing subsequence of an array.
Open on GeeksforGeeks ↗Intuition
This looks like Longest Increasing Subsequence, but optimising sum instead of length changes which chain wins — the longest chain is not always the heaviest, so [1,2,3] loses to [100]. The state is the same shape though: dp[i] = the best sum of an increasing subsequence that ends at index i. Anchoring at i is what makes the recurrence work, because any chain ending at i must arrive from some earlier, smaller element whose own best sum is already known.
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
Anchor the state at an index
dp[i] = maximum sum of an increasing subsequence ending exactly at i. Initialise dp[i] = nums[i]: every element is a valid one-element subsequence.
Extend from smaller predecessors
For each j < i with nums[j] < nums[i], the chain ending at j can be extended: dp[i] = max(dp[i], dp[j] + nums[i]).
Answer is the maximum, not the last cell
The heaviest chain may end anywhere, so return max(dp) rather than dp[n-1].
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.