6.1

Maximum-Sum Contiguous Subsequence

Pattern · "ending at i" prefix 1-D table O(n) 2difficulty
Question — exam style

A contiguous subsequence of a list is a subsequence made up of consecutive elements. For instance, if the list is 5, 15, −30, 10, −5, 40, 10, then 15, −30, 10 is a contiguous subsequence but 5, 15, 40 is not. Design a dynamic-programming algorithm for the following task.

Input:A list of numbers a[1], a[2], …, a[n].
Output:The sum of the contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).

Model answer

4-part format
aSubproblem in words
T(i) = the maximum sum of a contiguous subsequence of a[1..i] that ends at (includes) a[i].

The "includes a[i]" constraint is what makes this a prefix problem: forcing the segment to end at i lets each entry extend the previous one in O(1).

bRecurrence math only, with base case + bounds
T(0) = 0 (empty prefix) T(i) = a[i] + max{ 0, T(i-1) } for 1 ≤ i ≤ n

Either extend the best segment ending at i−1, or drop it and start fresh at a[i] (the max{0, …} branch). Defining T(0)=0 makes T(1)=a[1] fall out correctly — consistent with the "ends at a[i]" definition, which forces every T(i) to contain a[i].

cImplementation analysis
(1) # of subproblems
O(n)
(2) Time to fill table
O(n)
(3) Where answer is extracted
max{ maxi T(i), 0 }
(4) Time to extract
O(n)
The extraction bug to avoid

Extraction must be max{ maxi T(i), 0 } — not plain max{T(*)}. Because the subproblem forces each segment to include a[i], every table entry holds at least one element. On an all-negative array, max{T(*)} returns the least-negative element; the empty-subsequence clause requires 0. The explicit , 0 is the fix.

Why scan the table at all, not T(n)

Because entries are pinned to end at i, the best overall segment can end anywhere, so you take the max over all i. Same reasoning as LIS. Contrast LCS, where the answer is simply T(n,m).

Optional pseudocode not required by Ed #9

A mechanical translation of the recurrence. The exam grades the recurrence, not this — but here's the fill loop if you want it.

function MaxSubarray(a[1..n]):
    T[0] = 0
    best = 0
    for i = 1 to n:
        T[i] = a[i] + max(0, T[i-1])
        best = max(best, T[i])
    return best              # = max{ max_i T(i), 0 }
✎

Try it yourself

worked example + self-test

Recurrence: T(0)=0; T(i)=a[i]+max{0,T(i-1)}. Answer max{maxi T(i), 0}.

Worked table trace shown

a = [ 5, 15, −30, 10, −5, 40, 10 ] (1-indexed)

i │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 ──────┼───┼────┼────┼─────┼────┼────┼────┼──── a[i] │ – │ 5 │ 15 │ −30 │ 10 │ −5 │ 40 │ 10 T(i) │ 0 │ 5 │ 20 │ −10 │ 10 │ 5 │ 45 │ 55 each: T(i) = a[i] + max{0, T(i−1)} e.g. T(6) = 40 + max{0, 5} = 45; T(7) = 10 + max{0,45} = 55
Answer: max{55, 0} = 55, from subarray a[4..7] = [10, −5, 40, 10] (10−5+40+10 = 55).
Self-test work the table, then reveal

a = [ −2, −5, 6, −2, −3, 1, 5, −6 ] (leading-negative run — the max{0,·} clamp resets it)

Reveal answer
Answer: 7, from subarray [6, −2, −3, 1, 5] = a[3..7].  Bonus edge: for an all-negative array like [−3,−1,−4,−2] the answer is 0 (empty subsequence wins).