Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:


Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.


Example 2:


Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Difficulty: interview

Starter code:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         def prod(nums):
             #function to calculate product
             prod = 1
             for i in nums:
                 prod*=i
             return prod
         def listsplit(ls1,index):
             result = []
             st = -1
             for i in index:
                 if i == 0:
                     st = i
                 else:
                     result.append(ls1[st+1:i])
                     st = i
             if st<len(ls1)-1:
                 result.append(ls1[st+1:])
             return result
         
         #main starts here
         if not nums:
             return 0
         if len(nums) == 1:
             return nums[0]
         #find zeros: if zeros are included the result would be zeros only
         result=[]
         if 0 in nums:
             zeros = [i for i in range(len(nums)) if nums[i] ==0]
             sublist = listsplit(nums,zeros)
             result.append(0)
         else:
             sublist = [nums]
         #find negative numbers. consider even or odd
         sublist = [i for i in sublist if i]
         
         for i in sublist:
             if prod(i) <0:
                 #there is negative number in the list
                 negative = [j for j in range(len(i)) if i[j] < 0]
                 left,right = negative[0],negative[-1]
                 if len(i) == 1:
                     result_t = i[0]
                 elif left == 0 or right == len(i) -1:
                     result_t = max(prod(i[left+1:]),prod(i[:right]))
                 else:
                     left_p,right_p = prod(i[:left]),prod(i[right+1:])
                     if left_p <= right_p:
                         result_t = prod(i[left+1:])
                     else:
                         result_t = prod(i[:right])
             else:
                 result_t = prod(i)
             result.append(result_t)
         return max(result)

class Solution:
 
 	def maxProduct(self, nums):
 		self._prod_cache = {}
 		m_value = None
 		if len(nums)==1:
 			return nums[0]
 		if len(nums)==0:
 			return 0
 		for i in range(len(nums)):
 			a_value = self.get_max_prod(nums, i, 1)
 			if m_value is None or a_value>m_value:
 				m_value = a_value
 		return m_value
 
 	def get_max_prod(self, nums, i, acc_p):
 		if i<0:
 			return None
 		if (i, acc_p) in self._prod_cache:
 			return self._prod_cache[(i, acc_p)]
 		val = nums[i]
 		if i>0:
 			max_p = max(self.get_max_prod(nums, i-1, acc_p*val),
 					   acc_p*val)
 		else:
 			max_p = acc_p*val
 
 		self._prod_cache[(i, acc_p)]=max_p
 		return max_p


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n=len(nums)		
         if n==0: return 0
         if n==1: return nums[0]
         ans=nums[0]
         l=0
         r=n-1 
         prod=1
 
         i=0
         while i<n:
             if nums[i]==0:
                 zero_idx=i
                 return max(self.maxProduct(nums[(zero_idx+1):]), max(0,self.maxProduct(nums[0:zero_idx])))
             else:
                 prod=prod*nums[i]
                 i=i+1
 		
 
         if prod>0: return prod
         prod_right=prod
         max_prod_right=prod
 		
         prod_left=prod
         max_prod_left=prod
 		
         if prod<0:
             #print(max_prod_right)           
             while 0<=r:
                 prod_right=prod_right//nums[r]
                 r=r-1
                 if prod_right>max_prod_right:
                     if prod_right>0:
                         max_prod_right=prod_right
                         break
                     else:
                         max_prod_right=prod_right
 						
 		    
             print(max_prod_left)
             while l<n:
                 prod_left=prod_left//nums[l]
                 l=l+1
                 #print(l, prod_left,"----", nums[l], nums[l:])
                 if prod_left>max_prod_left:
                     if prod_left>0:
                         max_prod_left=prod_left
                         break
                 else:
                     max_prod_left=prod_left
 
         #print(max_prod_left, max_prod_right)			
         return max(max_prod_left, max_prod_right)
 		


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums: return 0
         res = premax = premin = nums[0]
         curmax = curmin = None
         for n in nums[1:]:
             curmax, curmin = max(premax*n, premin*n, n), min(premax*n, premin*n, n)
             premax, premin = curmax, curmin
             res = max(res, curmax)
         return res


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         glo_max = nums[0]
         
         imax = glo_max
         imin = glo_max
         i = 1
         
         while i < len(nums):
             
             
             if nums[i] < 0:
                 temp = imax
                 imax = imin
                 imin = temp
             
             imax = max(nums[i], nums[i] * imax)
             imin = min(nums[i], nums[i] * imin)
             
             
             glo_max = max(glo_max, imax)
             i += 1
         
         return glo_max

class Solution(object):
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         # track min_negative_product and max_positive_product
         
         
         if len(nums) == 0:
             return nums
         if len(nums) == 1:
             return nums[0]
         
         curr_min = curr_max = best_max = nums[0]
         
         for i in range(1,len(nums)):
             curr_min,curr_max = min(nums[i],nums[i]*curr_min,nums[i]*curr_max),max(nums[i],nums[i]*curr_min,nums[i]*curr_max)
             
             best_max = max(curr_max,best_max)
             
         return best_max

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         dp_max=[0]*len(nums)
         dp_min=[0]*len(nums)
         res=dp_max[0]=dp_min[0]=nums[0]
         
         for i in range(1,len(nums)):
             dp_max[i]=max(nums[i],dp_max[i-1]*nums[i],dp_min[i-1]*nums[i])
             dp_min[i]=min(nums[i],dp_max[i-1]*nums[i],dp_min[i-1]*nums[i])
             res=max(res,dp_max[i])
         return res

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_val = -float("inf")
         product = 1
         for num in nums:
             product *= num
             max_val = max(product, max_val)
             if num == 0:
                 product = 1
         product = 1
         for num in nums[::-1]:
             product *= num
             max_val = max(product, max_val)
             if num == 0:
                 product = 1
         return max_val

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         res = loc_min = loc_max = nums[0]
         for i in nums[1:]:
             if i < 0:
                 loc_min, loc_max = loc_max, loc_min
             loc_min = min(i, loc_min * i)
             loc_max = max(i, loc_max * i)
             res = max(loc_min, loc_max, res)
         return res

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums[0]
 
         else:
             result = big = small = nums[0]
         for i in nums[1:]:
             big, small = max(i, i*big, i*small), min (i,i*small, i*big)
             result = max(result, big)
         return result
 
                     
                 
                 


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         dp = [[nums[0], nums[0]]] * n
         ans = nums[0]
         for i in range(1, n):
             temp = [dp[i-1][0] * nums[i], dp[i-1][1] * nums[i], nums[i]]
             dp[i][0], dp[i][1] = max(temp), min(temp)
             if dp[i][0] > ans:
                 ans = dp[i][0]
         return ans

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         dp = [[nums[0], nums[0]] for _ in range(n)]
         ans = nums[0]
         for i in range(1, n):
             temp = [dp[i-1][0] * nums[i], dp[i-1][1] * nums[i], nums[i]]
             dp[i][0], dp[i][1] = max(temp), min(temp)
             if dp[i][0] > ans:
                 ans = dp[i][0]
         return ans
     
 #        n = len(nums)
 #        dp = [[nums[0], nums[0]]] * n   尽量不要使用乘法
 #        ans = nums[0]
 #        for i in range(1, n):
 #            temp = [dp[i-1][0] * nums[i], dp[i-1][1] * nums[i], nums[i]]
 #            dp[i][0], dp[i][1] = max(temp), min(temp)   这样赋值会改变所有值
 #            if dp[i][0] > ans:
 #                ans = dp[i][0]
 #        return dp[-1][0]


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         f = [[nums[0], nums[0]]]
         ans = nums[0]
         for i in range(1, len(nums)):
             f.append([0, 0])
             f[i][0] = min(f[i-1][0]*nums[i], f[i-1][1]*nums[i], nums[i])
             f[i][1] = max(f[i-1][0]*nums[i], f[i-1][1]*nums[i], nums[i])
             ans = max(ans, f[i][1])
         return ans

class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         largestproduct = []
         smallestproduct = []
         n =len(nums)
         largestproduct.append(nums[0])
         smallestproduct.append(nums[0])
         for i in range(n-1):
             lp = max(max(largestproduct[i]*nums[i+1],smallestproduct[i]*nums[i+1]),nums[i+1])
             sp = min(min(largestproduct[i]*nums[i+1],smallestproduct[i]*nums[i+1]),nums[i+1])
             largestproduct.append(lp)
             smallestproduct.append(sp)
         sol = largestproduct[0]
         for i in range(n):
             sol = max(sol,largestproduct[i])
         return sol


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxPos = nums[0]
         maxNeg = -nums[0]
         p = 1
         result = nums[0] 
         while p < len(nums):
             if nums[p] >= 0:
                 tmp1 = max(nums[p], nums[p] * maxPos)
                 tmp2 = max(-nums[p], nums[p] * maxNeg) 
                 maxPos = tmp1
                 maxNeg = tmp2
             else:
                 tmp1 = max(nums[p], -nums[p] * maxNeg)
                 tmp2 = max(-nums[p], -nums[p] * maxPos)
                 maxPos = tmp1
                 maxNeg = tmp2
             print((nums[p], maxPos, maxNeg))
             result = max(result, maxPos)
             p += 1
         return result
     
 


class Solution:
     def maxProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxP = nums[0]
         minP = nums[0]
         p = 1
         result = nums[0] 
         while p < len(nums):
             tmp1 = max(nums[p], nums[p] * maxP, nums[p] * minP)
             tmp2 = min(nums[p], nums[p] * maxP, nums[p] * minP) 
             maxP = tmp1
             minP = tmp2
             print((nums[p], maxP, minP))
             result = max(result, maxP)
             p += 1
         return result