152. 乘积最大子数组(Medium)

题解

视频题解：https://www.bilibili.com/video/BV1wA411b7qZ?p=26

Python示例

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums: return 0
        minProductDp = [0] * len(nums)
        maxProductDp = [0] * len(nums)
        minProductDp[0] = maxProductDp[0] = ans = nums[0]
        
        for i in range(1, len(nums)):
            minProductDp[i] = min(nums[i], 
                                  nums[i] * minProductDp[i - 1],
                                  nums[i] * maxProductDp[i - 1])
            maxProductDp[i] = max(nums[i], 
                                  nums[i] * minProductDp[i - 1],
                                  nums[i] * maxProductDp[i - 1])
            ans = max(ans, maxProductDp[i], minProductDp[i])
        return ans 

func max(nums ...int) int{
   ans := nums[0]
   for i:= 1; i < len(nums); i++ {
       if nums[i] > ans {
           ans = nums[i]
       }
   }
   return ans 
}

func min(nums ...int) int{
   ans := nums[0]
   for i:= 1; i < len(nums); i++ {
       if nums[i] < ans {
           ans = nums[i]
       }
   }
   return ans 
}

func maxProduct(nums []int) int {
   if len(nums) == 0 {
      return 0
   }
   if len(nums) == 1 {
       return nums[0]
   }

   maxProductMemo := make([]int, len(nums))
   minProductMemo := make([]int, len(nums))
   maxProductMemo[0] = nums[0]
   minProductMemo[0] = nums[0]
   for i:= 1; i < len(nums); i++ {
       maxProductMemo[i] = max(nums[i], 
                               maxProductMemo[i - 1] * nums[i],
                               minProductMemo[i - 1] * nums[i])
       minProductMemo[i] = min(nums[i], 
                               maxProductMemo[i - 1] * nums[i],
                               minProductMemo[i - 1] * nums[i])              
   }
   return max(maxProductMemo...)
}