|
题目来源：https://leetcode-cn.com/problems/maximum-product-subarray/
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
解法一：动态规划
考虑几种情况：
- 数组中没有负数，全是正数：全部相乘为最大乘积
- 数组中有偶数个负数：全部相乘为最大乘积
- 数组中有奇数个负数：要么取第一个负数之后的所有数相乘，要么取最后一个负数之前的所有数相乘（保证偶数个负数，相乘得到正数）
为此，维护两个值：最大值和最小值，状态转移方程：
- max_ = max(max_ * num, min_*num, num)
- min_ = min (max_*num, min_*num, num)
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
res = nums[0]
pre_max = nums[0] # 最大值
pre_min = nums[0] # 最小值
for i in range(1, n):
cur_max = max(pre_max * nums[i], pre_min * nums[i], nums[i]) # 更新
cur_min = min(pre_max * nums[i], pre_min * nums[i], nums[i]) # 更新
res = max(res, cur_max)
pre_max = cur_max
pre_min = cur_min
return res
参考：
https://leetcode-cn.com/problems/maximum-product-subarray/solution/duo-chong-si-lu-qiu-jie-by-powcai-3/ | 
转播
