maximum_subarray.py

from typing import List


class Solution:
    """LeetCode #53 - Maximum Subarray (Medium)
    https://leetcode.com/problems/maximum-subarray/

    Return the largest sum of any contiguous non-empty subarray. Values may be
    negative, which is what makes it interesting.
    """

    def maxSubArray(self, nums: List[int]) -> int:
        """Kadane's algorithm - drop the prefix as soon as it turns negative.

        Key insight: walk left to right carrying the best sum of a subarray that
        *ends at the current position*. Extending it is only worth it while the
        running sum is positive - the moment it goes negative, that prefix can
        only drag down whatever follows, so the best move is to abandon it and
        start fresh at the next element.

        Put differently: a negative prefix is never a useful thing to carry, and
        that single observation collapses the O(n^2) pair scan into one pass.

        `best` is seeded with nums[0] rather than 0 because the subarray must be
        non-empty - for an all-negative input like [-3, -1, -2] the answer is
        -1, and starting from 0 would wrongly report 0.

        Time:  O(n) - one pass.
        Space: O(1)
        """
        best = nums[0]
        current = 0        # sum of the subarray ending at the previous index

        for x in nums:
            if current < 0:
                current = 0    # the prefix hurts - restart the subarray here
            current += x
            best = max(best, current)

        return best

        # Follow-up interviewers like: to also return the indices, remember
        # where `current` was restarted and update the stored bounds whenever
        # `best` improves.