152. Maximum Product Subarray

Description:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

'''
[1] brute force)

idea::
using two pointer(nested-loop), find max product.

code::
def maxProduct(self, nums: List[int]) -> int:
    max_pro=-float(inf)
    for i in range(len(nums)):
        cur_pro=1
        for j in range(i,len(nums)):
            cur_pro*=nums[j]
            max_pro=max(max_pro,cur_pro)
    return max_pro
    
-T/C: O(n^2)
-S/C: O(1)
'''

'''
[2] dp and kadane's algorithm)

idea::
need to keep cur_min and cur_max, because when meet negative number, need to check negative * negative

code::
(below)

-T/C: O(n) # one-pass
-S/C: O(1)
'''
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # init
        cur_max,cur_min,max_prod=nums[0],nums[0],nums[0]
        
        # dp
        for i in range(1, len(nums)):
            # for calculating cur_min
            tmp=cur_max
            
            cur_max=max(nums[i],nums[i]*cur_max,nums[i]*cur_min)
            cur_min=min(nums[i],nums[i]*tmp,nums[i]*cur_min)
            
            max_prod = max(cur_max, max_prod)
        return max_prod