maximum_product_subarray.py

from typing import List


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

    Largest product of a contiguous subarray.
    """

    def maxProduct(self, nums: List[int]) -> int:
        """Kadane, but carrying two running values instead of one.

        Sums only ever get worse when a prefix is negative, so Kadane drops it.
        Products do not: a very negative running product becomes the maximum the
        moment another negative arrives. So the minimum has to be carried too,
        and a negative number swaps their roles.

        Zeros reset both, which falls out of taking max/min against `num` itself
        rather than special-casing them.

        Time:  O(n)
        Space: O(1)
        """
        best = high = low = nums[0]

        for num in nums[1:]:
            if num < 0:
                high, low = low, high      # a negative turns the best into the worst

            high = max(num, high * num)
            low = min(num, low * num)
            best = max(best, high)

        return best