leetcode [152] 乘积最大子序列

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例 1:

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

示例 2:

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

交替迭代最大最小值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxval = -999
        imax = 1
        imin = 1
        for n in nums:
            if n < 0: 
                imax, imin = imin, imax
            imax = max(imax * n, n)
            imin = min(imin * n, n)
            maxval = max(maxval, imax)
        
        return maxval

保持记录最大值和最小值，当前的最大值和最小值为 乘以当前值或者当前值的最大值和最小值，注意赋值的时候不能分开写，会导致覆盖，因此需要同时赋值，或者开一个数组保存历史值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -99999
        maxval, minval = 1, 1
        for n in nums:
            maxval, minval = max(maxval * n, minval * n, n),  min(maxval * n, minval * n, n)
            ans = max(ans, maxval)
        return ans