Maximum Subarray

def maxSubArray(nums):
    cur = best = nums[0]    # pack, flag
    for x in nums[1:]:
        cur = max(x, cur + x)    # drop or carry
        best = max(best, cur)    # move the flag
    return best

Maximum Subarray. Find the contiguous run of an array with the largest sum, and return that sum.

Here's the example: minus two, one, minus three, four, minus one, two, one, minus five, four. The best run is four, minus one, two, one: a sum of six.

The naive way tries every start, then extends the run to every end, adding as it goes. That's forty-five runs for just nine numbers, about n squared. Too slow for big arrays.

The key idea is Kadane's algorithm. A hiker walks the array once, with a backpack holding the running total. Each number moves the trail up or down. If the pack goes negative, it only drags down what comes next, so drop it and start fresh. Plant a flag at the highest point so far.

In code, cur is the pack and best is the flag. For each number, cur becomes the bigger of the number alone, or cur plus the number. Best keeps the larger of itself and cur.

Let's hike. Minus two: the pack and the flag hold minus two. At one, the pack is negative, so drop it and start fresh: one, a new flag. Minus three brings it to minus two. At four, drop it again: four, a new flag. Minus one, two and one take the pack to three, five, then six: the flag moves to six. Minus five falls to one, and four climbs back to five. The flag stays at six.

One pass, so the time is O of n. And just two numbers to remember, so the space is O of one.

Drop the negative pack, keep the highest flag. That's Maximum Subarray.