Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence is the classic "Longest Increasing Subsequence" with one twist: instead of counting how many elements you pick, you add up their values and chase the biggest total. It is a clean introduction to dynamic programming over an array.

The slow way first

The brute-force idea is to enumerate every subsequence, throw away the ones that are not increasing, and take the largest remaining sum. There are 2^n subsequences, so this is exponential — hopeless past a tiny array.

The question to ask: if I commit to ending my subsequence at element a[i], what is the best sum I can reach? If I knew that answer for every earlier element, I could build a[i]'s answer from them. That is exactly what dynamic programming gives us.

The idea: best sum ending here

Define dp[i] = the largest sum of an increasing subsequence that ends at index i. Every element on its own is a valid (length-1) subsequence, so dp[i] starts at a[i].

To improve it, look at every earlier index j < i. If a[j] < a[i], then a[i] can be appended to the run ending at j, giving dp[j] + a[i]. Keep the best such extension:

dp[i] = max(a[i], max over j<i with a[j]<a[i] of (dp[j] + a[i]))

The final answer is max(dp) — the best run can end anywhere.

Walk through it

Step through the animation. The top row is a; the bottom row is the dp table. The pointer i picks the element we are filling; j sweeps every earlier element. When a[j] < a[i], that earlier run is a candidate, and we slide its sum plus a[i] into dp[i]. Watch how the greedy-looking 101 ends with dp = 102 but is a dead end, while the patient 1, 2, 3, 100 chain builds up to 106.

Pseudocode

dp = copy of a                          # each element alone is its own sum
for i from 1 to n-1:
    for j from 0 to i-1:
        if a[j] < a[i]:                 # a[i] can follow this earlier run
            dp[i] = max(dp[i], dp[j] + a[i])
return max(dp)                          # best run can end anywhere

The Python solution

def max_sum_is(a):
    n = len(a)
    dp = a[:]
    for i in range(1, n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + a[i])
    return max(dp)

• dp = a[:] copies the array so every dp[i] starts at a[i] — the trivial subsequence of just that element.
• The outer loop fixes the endpoint i of the subsequence.
• The inner loop scans every earlier index j as a possible predecessor.
• if a[j] < a[i] is the increasing check — only smaller earlier values may come before a[i].
• dp[i] = max(dp[i], dp[j] + a[i]) keeps the best sum: either what we had, or extending the run ending at j.
• return max(dp) — the optimal subsequence may end at any index, so we scan the whole table.

Complexity

The dp array is the only extra storage, so space is O(n). The two nested loops give O(n²) time — a massive improvement over enumerating all 2^n subsequences.

When this pattern shows up

Practice