Maximum Subarray

Learning goal: Recognize that the answer must come from a contiguous, non-empty portion of the array.

Core idea We scan the array while deciding which subarray should end at each position. A negative prefix can make every later candidate worse, so we need the option to discard that prefix and begin again. Because the subarray cannot be empty, negative inputs require careful initialization.

Algorithm plan

• Visit each number from left to right.
• Maintain the best sum of a subarray ending at the current index.
• Maintain the largest sum seen anywhere so far.
• Return the overall maximum after the scan.

Micro-example For [-2, 1], the best subarray ending at 1 is either [1] with sum 1 or [-2,1] with sum -1. Choose 1, so the earlier negative prefix is discarded.

Pitfalls

• The subarray must be non-empty.
• Initializing the answer to 0 is wrong for all-negative arrays.
• Do not confuse the best ending here with the best answer overall.

Recap

• Contiguous elements are required.
• Each index gives a local ending-at-index decision.
• Preserve negative answers through initialization.

Learning goal: Understand the single local choice that makes Kadane's algorithm work.

Core idea Suppose current is the best sum of a subarray that ends immediately before num. A subarray ending at num has only two meaningful forms: extend that earlier subarray, giving current + num, or restart at num, giving num. Taking the larger value preserves the best possible ending sum without remembering every subarray.

Recurrence

current = max(num, current + num)

best = max(best, current)

Micro-example Before 4, suppose current = -4. Extending gives 0, while restarting gives 4. The algorithm chooses 4, beginning a new candidate at that index.

Pitfalls

• Compare against the element itself, not only against zero.
• Update best after computing the new current.
• A negative current is not automatically the final answer; a later value may be larger.

Recap

• Extend with current + num or restart with num.
• current describes subarrays ending at one index.
• best records the strongest result seen anywhere.

Learning goal: Translate the recurrence into a constant-space one-pass algorithm.

Core idea The dynamic-programming state conceptually has one value per index, but each state depends only on the previous state. Therefore, two variables are enough: current for the best subarray ending at the current position and best for the overall maximum.

Algorithm plan

1. Initialize both values from nums[0].
2. For every later num, compute current = max(num, current + num).
3. Update best = max(best, current).
4. Return best.

current = best = nums[0]
for num in nums[1:]:
    current = max(num, current + num)
    best = max(best, current)
return best

Micro-example For [-2,1,-3], the states are: current = -2, then 1, then -2. The overall values are -2, 1, 1, so the answer is 1.

Pitfalls

• Starting at index 0 preserves the non-empty requirement.
• Update current before comparing it with best.
• Do not store the whole DP array when only the previous state is needed.

Recap

• One pass computes every local state.
• Two scalar variables replace an entire DP table.
• The recurrence directly expresses extend versus restart.

Learning goal: Trace current and best from start to finish on a concrete input.

Core idea We use [-2,1,-3,4,-1,2,1,-5,4], the first example above. At each index, current answers a local question: what is the best sum of a non-empty subarray ending exactly here? The variable best answers the global question across all positions processed so far.

Recurrence

Micro-example At 4, the prior current is -2. Extending gives 2, but restarting gives 4, so current becomes 4. The later values -1, 2, 1 extend this run to 6.

Pitfalls

• A restart does not mean the algorithm stops; scanning continues.
• best remains 6 even when current falls to 1 after -5.
• The final answer is not necessarily the final current in other inputs.

Recap

• The best segment is [4,-1,2,1].
• Its sum becomes the global maximum at index 6.
• Every update uses only the previous local state.

Learning goal: Handle negative-only arrays and initialization correctly.

Core idea The most common bug is setting best = 0. That silently permits an empty subarray, which the problem forbids. If all values are negative, the correct answer is the least-negative element, so initialization must come from nums[0], not from zero.

Algorithm plan

• Initialize current and best to the first number.
• Process the remaining numbers with the extend-or-restart recurrence.
• Let each number compete directly as a possible one-element answer.

Micro-example Start with current = best = -8. At -3, current = max(-3,-11) = -3, so best becomes -3.

Pitfalls

• Do not use zero as the initial maximum.
• Do not return zero when the running sum becomes negative.
• Handle a one-element array directly through initialization.

Recap

• Non-empty means every element is a valid candidate.
• First-element initialization handles all-negative inputs.
• The recurrence never needs a special negative-number branch.

Learning goal: Explain why Kadane's algorithm meets the target bounds.

Core idea Each array element is examined exactly once, and each examination performs a constant amount of arithmetic and comparison. The algorithm stores only current and best, so its extra memory does not grow with the input length.

Algorithm plan

• Read each number once from left to right.
• Compute one extend-or-restart maximum.
• Update one global maximum.
• Return the global maximum.

Micro-example For an array of length n, the loop performs n - 1 updates after initialization. Whether n is 10 or 100,000, no element requires a second scan.

Pitfalls

• A full DP array is correct but unnecessary when only the previous state is needed.
• Brute force repeats work across many overlapping subarrays.
• Space complexity counts extra storage, not the input array itself.

Recap

• Time: O(n).
• Extra space: O(1).
• The winning pattern is: extend when useful, otherwise restart; always preserve the best answer seen.