# 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/>

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

```python
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])

```python
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`情况,重置就可以了

```python
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

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