Maximum Sum Increasing Subsequence - Walkthrough

Find increasing subsequence with maximum sum. The DP tracks sum instead of length. $dp[i]$ = maximum sum of increasing subsequence ending at $i$.

Base: $dp[i] = nums[i]$. Transition: $dp[i] = \max(nums[i], \max(dp[j] + nums[i]))$ for all $j < i$ with $nums[j] < nums[i]$. Example: $[1, 101, 2, 3, 100, 4, 5]$. Max sum IS is $[1, 2, 3, 100]$ with sum $106$, not the longest $[1, 2, 3, 4, 5]$ with sum $15$.