Maximum Subarray

The machine must find the contiguous subarray with the largest sum and return that sum. The key insight is local: the maximum sum ending at index i is either the element itself or the element plus the best subarray ending at i-1. You don't need to know where the subarray starts — only whether the running best is worth extending. This is Kadane's algorithm, a degenerate dynamic program with a single state variable.

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

Steps: (1) start both the running sum and the answer at the first element, (2) for each next element, decide: restart here, or extend, (3) track the largest running sum.

Time is O(n), one pass. Space is O(1).

Trickiest edge case: an array of all negative numbers, like [-1,-2,-3]. current = max(num, current + num) still finds -1, because restarting at each element beats extending. If you initialized best = 0, the answer would be 0 — wrong. Initializing to nums[0] (or negative infinity) is mandatory.