'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

class Solution:
    # T: O(N) and S: O(1)
    def maxProduct1(self, nums: List[int]) -> int:
        # store the result that is the max we find so far
        res = nums[0]
        n = len(nums)
        
        # imax/imin stores the max/min product of 
        # subarray that ends with the current number A[i]
        imax = imin = res
        for i in range(1, n):
            # multiplied by a negative makes big number smaller, small number bigger
            # so we redefine the extremums by swapping them
            if nums[i] < 0:
                tmp = imax
                imax = imin
                imin = tmp
            # max/min product for the current number is either the current number itself
            # or the max/min by the previous number times the current one
            imax = max(nums[i], imax * nums[i])
            imin = min(nums[i], imin * nums[i])
            # the newly computed max value is a candidate for our global result
            res = max(res, imax)
        return res
    
    
    # a tricky one; T: O(N); S: O(N) 
    def maxProduct(self, nums: List[int]) -> int:
        rev = nums[::-1]
        for i in range(1, len(nums)):
            # prefix product
            # if nums[i-1] != 0: nums[i] *= nums[i-1]
            nums[i] *= nums[i-1] or 1
            # suffix product
            rev[i] *= rev[i-1] or 1
        return max(nums + rev)
        
        