184 - 152 乘积最大子序列

题目

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

示例 1:

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

示例 2:

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

解答

感觉可以动态规划，建立一张一样大的dp表，记录至今最大的乘积

不过这个思路好像不行，反例是[-2,3,-4]，应该输出24，但贪心记录最大值，就不行了

存最大值和最小值

https://leetcode-cn.com/problems/maximum-product-subarray/solution/hua-jie-suan-fa-152-cheng-ji-zui-da-zi-xu-lie-by-g/

记录当前最大值和最小值，如果当前数字是负数，就交换二者

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        imax = 1
        imin = 1
        res = float('-inf')
        for num in nums:
            if num < 0:
                imax, imin = imin, imax
            imax = max(imax*num, num)
            imin = min(imin*num, num)
            res = max(res, imax)
        return res

Runtime: 60 ms, faster than 66.82% of Python3 online submissions for Maximum Product Subarray.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Maximum Product Subarray.

动态规划

https://leetcode-cn.com/problems/maximum-product-subarray/solution/duo-chong-si-lu-qiu-jie-by-powcai-3/

dp[i] = max(nums[i] pre_max, nums[i] pre_min, nums[i])

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return
        res = nums[0]
        imax = nums[0]
        imin = nums[0]
        for num in nums[1:]:
            cur_max = max(imax*num, imin*num, num)
            cur_min = min(imax*num, imin*num, num)
            res = max(res, cur_max)
            imax = cur_max
            imin = cur_min
        return res

Runtime: 56 ms, faster than 81.34% of Python3 online submissions for Maximum Product Subarray.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Maximum Product Subarray.

负号个数

当负数个数为偶数时候, 全部相乘一定最大

当负数个数为奇数时候，把数组从中间切开, 左右两边的负数个数一定为偶数, 只需求两边最大值

当有0情况,重置就可以了

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        reverse = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i-1]or 1
            reverse[i] *= reverse[i-1]or 1
        return max(nums+reverse)

Runtime: 48 ms, faster than 97.26% of Python3 online submissions for Maximum Product Subarray.

Memory Usage: 13.9 MB, less than 27.59% of Python3 online submissions for Maximum Product Subarray.

这个or 1意味着，如果是0，就取1

数组相加就是两个数组拼起来，然后取其中的最大值