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.
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
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.