Maximum subarray: sum, product and circular

The maximum subarray problem asks for the stretch of consecutive values with the largest total, such as the best run of days in a shop’s profit-and-loss ledger. Kadane’s algorithm solves it in one pass by keeping the best total of a stretch that ends at the current position, which is why it belongs with linear DP. Two variants come up often. The maximum product of a stretch changes what must be kept, because a negative value turns the smallest product into the largest and a zero ends every stretch through it. The circular version lets a stretch wrap from the last value to the first. This lesson poses all three on original data.

Three problems on one row of numbers

Problem A, the best stretch of a ledger. A shop records each day’s profit or loss. Return the largest total of a non-empty stretch of consecutive days. Limits: 1 ≤ n ≤ 200,000 and −10,000 ≤ ledger[i] ≤ 10,000.

• [3, −5, 4, −1, 2, 6, −8, 1] gives 11, from days 2 to 5.
• [−7, −2, −9] gives −2: a loss on every day, so the best stretch is the single smallest loss.

Problem B, the best product of a run of cards. A row of up to 200,000 number cards from −9 to 9; return the largest product of a run of consecutive cards. Every product of a run fits in a signed 64-bit integer.

• [2, −3, −2, 4, 0, −5] gives 48, from the first four cards.
• [−2, 0, −1] gives 0, the 0 on its own.

Problem C, a ledger in a ring. The same as A, but the last day is followed by the first, so a stretch may wrap. [5, −8, 2, 4, −9, 6] gives 11, from the last day and the first: 6 + 5.

The brute force, and why it fails

Try every start, and extend the stretch one value at a time while keeping its total or product:

def best_sum_brute(ledger):
    """Every stretch of consecutive days, its total kept as the end moves right: n(n + 1) / 2 stretches."""
    best, stretches = None, 0
    for start in range(len(ledger)):
        total = 0
        for end in range(start, len(ledger)):
            total += ledger[end]
            stretches += 1
            best = total if best is None else max(best, total)
    return best, stretches


def best_product_brute(cards):
    """The same for products: every run of consecutive cards, its product kept as the run grows."""
    best = None
    for start in range(len(cards)):
        product = 1
        for end in range(start, len(cards)):
            product *= cards[end]
            best = product if best is None else max(best, product)
    return best


for ledger in ([3, -5, 4, -1, 2, 6, -8, 1], [-7, -2, -9]):
    best, stretches = best_sum_brute(ledger)
    print(f"ledger {ledger}: best stretch {best} ({stretches} stretches tried)")
for cards in ([2, -3, -2, 4, 0, -5], [-2, 0, -1], [-3]):
    print(f"cards {cards}: best product {best_product_brute(cards)}")
n = 200_000
print(f"{n:,} days: {n * (n + 1) // 2:,} stretches")

ledger [3, -5, 4, -1, 2, 6, -8, 1]: best stretch 11 (36 stretches tried)
ledger [-7, -2, -9]: best stretch -2 (6 stretches tried)
cards [2, -3, -2, 4, 0, -5]: best product 48
cards [-2, 0, -1]: best product 0
cards [-3]: best product -3
200,000 days: 20,000,100,000 stretches

There are n(n + 1)/2 stretches: 36 for the first ledger, but 20,000,100,000 for 200,000 days, minutes of work even in C++. Recomputing each sum from scratch would cost another factor of n.

What to notice

• A stretch that ends on day i either extends the best stretch ending on day i − 1 or starts on day i. One number per day is enough to decide between them.
• For products, a negative card turns the smallest product into the largest, so the smallest must be carried too, and a 0 ends every run that crosses it.
• A stretch that wraps around leaves out one stretch in the middle, so the circular best is tied to the worst stretch.

Kadane’s algorithm, and the invariant that proves it Pro: opens with a Pro, Premium or Ultimate pass