Maximum SubarrayMaximum subarray

01Why it exists

Reach for it when you see:Contiguous subarray, largest sum, the best buy-and-sell window, the strongest stretch of a signal, something you can halve and then merge.

02The core idea

The maximum subarray problem: given a run of positive and negative numbers, find the contiguous stretch with the largest sum. Enumerating every (l, r) pair is O(n²), and a prefix-sum array only makes the inner summation O(1) — the enumeration itself is still n².

The divide and conquer observation is that once you cut the array down the middle, the winning range can only sit in one of three places: entirely in the left half, entirely in the right half, or across the middle. The first two are handled by recursion. The third must contain both mid and mid+1, so it equals "the best suffix ending at mid" plus "the best prefix starting at mid+1", each computed with one O(n) scan. Take the largest of the three. The recurrence T(n) = 2T(n/2) + n gives O(n log n) by the master theorem, with O(log n) space for the recursion depth.

Kadane comes at it from another angle: let cur be the largest sum of a run ending at element i. Either you extend the previous run with a[i] (cur + a[i]) or you restart from a[i], whichever is bigger. Put another way, if what you have accumulated so far is negative, carrying it forward only hurts, so throw it away. The overall answer is the largest cur you ever see. One pass, O(n) time and O(1) space. This is really one-dimensional DP, and you will meet it again under that topic.

Choosing between them: Kadane is faster and shorter, so write that in an interview. What makes divide and conquer worth knowing is the shape of its merge. A segment only needs four numbers — total sum, best prefix, best suffix, best subarray — for two adjacent segments to merge in O(1), and that is exactly how a segment tree answers range maximum-subarray queries. A common mistake: when every number is negative the answer is the largest negative one, not 0, so initialise best to a[0] rather than 0.

03The algorithm

1. 1Divide and conquer: solve(lo, hi) returns the maximum subarray sum inside that range. If lo == hi, return a[lo].
2. 2Take mid and recurse for left = solve(lo, mid) and right = solve(mid+1, hi).
3. 3Across the middle: accumulate leftwards from mid and keep the largest total as bestL; accumulate rightwards from mid+1 and keep the largest as bestR. The crossing answer is bestL + bestR.
4. 4Return max(left, right, bestL + bestR). Each level costs O(n) and there are log n levels.
5. 5Kadane: cur = max(a[i], cur + a[i]), best = max(best, cur), both initialised from a[0], in a single pass.

04Interactive demo

Eight days of price changes. The first half is divide and conquer: in the recursion tree, blue is the range being worked on and green is one already solved; in the array, yellow is the span of the cross-the-middle scan and green is this level's answer range. Once that finishes, the same run of steps continues with Kadane: yellow is the range cur currently covers and green is the best found so far — watch how two variables and one pass reach the same answer.

05Code

The divide-and-conquer version and Kadane side by side, plus a variant that reports the range itself — that is what the stock question's "which day to buy, which day to sell" needs.

# Maximum subarray (LeetCode 53): the divide-and-conquer version.
# The answer can only be in one of three places: all in the left half, all in the right half, or across the middle.
def max_subarray_dc(a):
    def solve(lo, hi):
        if lo == hi:
            return a[lo]                          # a single element
        mid = (lo + hi) // 2
        left = solve(lo, mid)                     # all in the left half
        right = solve(mid + 1, hi)                # all in the right half
        # Across the middle: best suffix ending at mid + best prefix starting at mid+1
        s, best_l = 0, float("-inf")
        for i in range(mid, lo - 1, -1):
            s += a[i]
            best_l = max(best_l, s)
        s, best_r = 0, float("-inf")
        for i in range(mid + 1, hi + 1):
            s += a[i]
            best_r = max(best_r, s)
        return max(left, right, best_l + best_r)  # take the best of the three
    return solve(0, len(a) - 1)


# Kadane: cur is the best sum ending at i. Drop it once it goes negative and start over.
def max_subarray_kadane(a):
    cur = best = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)                     # extend the run, or restart from x
        best = max(best, cur)
    return best


# Variant: also return the range [l, r]
def max_subarray_range(a):
    cur, best = a[0], a[0]
    start, l, r = 0, 0, 0
    for i in range(1, len(a)):
        if cur < 0:
            cur, start = a[i], i                  # start over
        else:
            cur += a[i]
        if cur > best:
            best, l, r = cur, start, i
    return best, l, r


if __name__ == "__main__":
    a = [-2, 1, -3, 4, -1, 2, 1, -5]
    print(max_subarray_dc(a), max_subarray_kadane(a), max_subarray_range(a))  # 6 6 (6, 3, 6)

06Practice

• LeetCode 121Best Time to Buy and Sell Stock (turn the prices into daily changes)Easy
• LeetCode 53Maximum Subarray (write it once with divide and conquer, once with Kadane)Medium
• LeetCode 152Maximum Product Subarray (track the maximum and the minimum together)Medium
• LeetCode 918Maximum Sum Circular Subarray (total minus the minimum subarray)Medium
• LeetCode 1186Maximum Subarray Sum with One DeletionMedium
• LeetCode 363Max Sum of Rectangle No Larger Than K (collapse two dimensions into one)Hard