Maximum Subarray (Kadane's Algorithm) — Guide

• Kadane: at each index, the best subarray ending here is either the element alone or the element plus the best ending at the previous index.
• Track the running sum, reset to 0 when it goes negative, and keep the global maximum.
• Divide-and-conquer gives O(n log n) and generalizes to 2D problems.

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

• Return the start and end indices of the maximum subarray.
• Maximum product subarray (track min and max because of negatives).
• Maximum subarray sum with at least k elements, or with one deletion allowed.