#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/maximum-sum-is-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/maximum-sum-is-implementation

Repovive

Maximum Sum Increasing Subsequence - Implementation - Longest Increasing Subsequence | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Maximum Sum Increasing Subsequence - Implementation

The code

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.