Solutions

# Variation of maximum subarray sum, but with products. Similar to Kadane's algorithm, but we need to keep track of both current max and min products at each step, because a negative number can flip the sign and make the min product become the max product.
# dp

# Kadane adapted for products - O(n) time, O(1) space
def maxProduct(nums: list[int]) -> int:
    if not nums:
        return 0

    # Negative numbers can flip the product sign, so we keep track of current min product too
    curMin, curMax = nums[0], nums[0] 
    res = curMax

    for n in nums[1:]:
        prod1 = curMin * n
        prod2 = curMax * n

        curMin = min(prod1, prod2, n)
        curMax = max(prod1, prod2, n)
        res = max(res, curMax)

    return res
    

# Brute force - O(n^2) time, O(1) space
def maxProduct(nums: list[int]) -> int:
    res = -99999
    for i in range(len(nums)):
        currprod = 1
        for j in range(i, len(nums)):
            currprod *= nums[j]
            res = max(res, currprod)
    return res