题目描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4],
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1],
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

最优解法——DP（AC）

记录当前最大, 最小值. 因为遇到负数时, 与最小值的product可能成为最大值.
如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。
- 记maxLast/minLast为连乘到上个元素的最大/小乘积
- 记maxCur/minCur为连乘到当前元素的最大/小乘积
动态转移方程式：
- max_copy[i] = max_local[i]
- max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]), min_local * A[i])
- min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]), min_local * A[i])
复杂度O(n)
Beat 85%

class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        maxlast = minlast = nums[0]
        maxcur = mincur = -1
        res = nums[0]
            
        for i in range(1,length):
            if(nums[i] < 0):
                maxcur = max(minlast * nums[i],nums[i])
                mincur = min(maxlast * nums[i],nums[i])
                    
            elif(nums[i] > 0):
                maxcur = max(maxlast * nums[i],nums[i])
                mincur = min(minlast * nums[i],nums[i])
                    
            else:
                maxcur = mincur = 0
                
            if(maxcur >= res):
                res = maxcur
            # print(str(maxcur) + str(mincur))
            maxlast = maxcur
            minlast = mincur
        
        return res