Maximum Subarray (Kadane)

Problem

Given an array of integers (positive, negative, or zero), find the contiguous subarray with the largest sum and return that sum.

My notes

Signal

"Best contiguous run" with no other constraints, over an array that can hold negative numbers, is a running-sum problem: carry a current-run total forward only while it's helping you, and drop it the moment it turns into dead weight.

Approach

Walk the array once, keeping a running sum of "the best subarray ending here." At each element, decide whether extending the previous run is better than starting fresh at this element: current = max(num, current + num). Track the best current seen across the whole walk — that's the answer.

Skeleton

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

Solution

def max_sub_array(nums: list[int]) -> int:
    current = best = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

Complexity

O(n) time — one pass. O(1) space — two running variables.

Pitfalls

"Reset to 0 when the running sum goes negative" is the version people memorize, but it's just a special case of max(num, current + num) — it breaks if all numbers are negative, since the true answer must still be a single (negative) element, not 0.
Initializing current/best to 0 instead of nums[0] silently allows an empty subarray to "win" when every number is negative.
This only answers "what's the sum" — if a follow-up asks for the actual subarray's indices, track the start index whenever you restart the run.