152 — Maximum Subarray

152 — Maximum Subarray

LeetCode 53 · Medium. Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

---

🍽️ Intuition

Imagine walking along nums left to right, keeping a running total of "the best sum of a subarray that ends right here." At each new number, you face exactly one choice: either extend the subarray that was already accumulating (add the new number to the running total), or abandon everything before it and start fresh from this number alone. Whichever produces a bigger running sum is strictly better for every subarray that might extend further to the right — so there's never a reason to keep the worse option around. The best subarray anywhere in the whole array is just the largest of these "best ending here" values, tracked as you go.

---

🚩 Pattern-Recognition Cue

"Maximum sum of a contiguous subarray" is the Kadane's-algorithm tell: at each position, the only locally relevant decision is "extend the running sum, or restart from here" — a single running-state greedy scan with no need to ever revisit an earlier position once it's been passed.

---

🐢 Brute Force

Check every possible subarray by trying every start and end pair, summing directly.

func maxSubArrayBruteForce(_ nums: [Int]) -> Int {
    var best = nums[0]

    for start in 0..<nums.count {
        var sum = 0
        for end in start..<nums.count {
            sum += nums[end]
            best = max(best, sum)
        }
    }

    return best
}

// smoke test
print(maxSubArrayBruteForce([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   // 6  ([4, -1, 2, 1])
print(maxSubArrayBruteForce([1]))                                // 1
print(maxSubArrayBruteForce([5, 4, -1, 7, 8]))                   // 23

Big-O: O(n^2) time — every one of the n possible start positions extends through every possible end position. O(1) extra space.

---

🚀 Optimal

Kadane's algorithm: at each position, greedily decide whether the running sum is worth keeping or worth abandoning in favor of starting over at the current element.

func maxSubArray(_ nums: [Int]) -> Int {
    var best = nums[0]
    var current = nums[0]

    for i in 1..<nums.count {
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    }

    return best
}

// smoke test — same cases as the brute force
print(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   // 6
print(maxSubArray([1]))                                // 1
print(maxSubArray([5, 4, -1, 7, 8]))                   // 23

Big-O: O(n) time — a single left-to-right pass over nums. O(1) extra space.

---

🔑 The Key Insight

The brute force treats every one of the n(n+1)/2 possible subarrays as its own independent thing to sum from scratch. But a subarray ending at position i only has two possible "sources": it's either the single element nums[i], or it's some best subarray ending at i - 1 with nums[i] tacked on. Since a negative running sum can only ever drag down whatever gets appended to it, there's never a reason to keep extending a running sum that has gone negative — restarting from the current element is always at least as good. That local, never-revisited decision at each position is exactly why the greedy scan finds the same answer as checking all O(n^2) subarrays, in linear time.

---

🔗 Related Chapters

• Greedy — a single left-to-right pass making one irrevocable local choice per element ("extend or restart") is the defining greedy shape, the same "running best-so-far" idea as Jump Game's farthest tracker.
• Arrays and Strings — both versions scan nums as a plain backing array, accumulating a running sum (or, in the brute force, every pairwise sum) as they go.

---

🧸 Memory Sentence

Maximum Subarray is Kadane's algorithm — at every position, either extend the running sum or abandon it and restart from here, keeping whichever running sum is largest as the answer.

---

✅ Check Your Understanding

1. Why is current = max(nums[i], current + nums[i]) correct — what does it mean, concretely, for current + nums[i] to lose to nums[i] alone at some position?
2. Trace maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) step by step. At which index does current "reset" by abandoning the running sum, and why is that the right call?
3. Why does the algorithm never need to remember where the current best subarray started, only its running sum?

---

⬅️ Previous: Regular Expression Matching · Next: Jump Game ➡️