Maximum Subarray

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
1D DPArraysOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Kadane’s Algorithm: any negative running prefix sum only lowers subsequent subarrays. Either extend the current subarray (`cur + x`) or start fresh at `x`: `cur = max(x, cur + x)`, `best = max(best, cur)`.

2. Complexity Bounds & Proof

Optimal subarray ending at index `i` depends solely on `max(0, dp[i-1]) + nums[i]`, executing in one O(1)-space pass.

3. Minimal Idiomatic Code

def maxSubArray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Initializing `best = 0` breaks on all-negative inputs (`[-5, -2, -8]` should return `-2`, not `0`). Initialize `best = cur = nums[0]`.
Follow-ups:- Divide and conquer in O(N log N) returns `(total, bestPrefix, bestSuffix, bestSub)` per segment (enables MapReduce / segment trees for range queries).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Product Subarray (O(N))Binary Tree Maximum Path Sum (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.