Maximum Sum Increasing Subsequence - Implementation

Here's the full solution:

function maxSumIS(nums)
    n := length of nums
    dp := copy of nums
    // base case: each element alone
    for i from 1 to n - 1
        for j from 0 to i - 1
            if nums[j] < nums[i]
                dp[i] := max(dp[i], dp[j] + nums[i])
    return max of dp array

Time: $O(n^2)$. Space: $O(n)$.

The structure matches LIS exactly. The only difference: instead of counting length, you sum values. dp[i] stores the maximum sum of any increasing subsequence ending at index $i$.

Base case: each element forms a subsequence of sum nums[i]. Transition: extend earlier subsequences if the current element is larger.