题目描述
LeetCode 152 — 乘积最大子数组 (Medium)
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1：
- 输入：
nums = [2,3,-2,4] - 输出：
6 - 解释：子数组
[2,3]的乘积最大，为6。
示例 2：
- 输入：
nums = [-2,0,-1] - 输出：
0 - 解释：结果不能为
2，因为[-2,-1]不是连续子数组。
示例 3：
- 输入：
nums = [-2,3,-4] - 输出：
24 - 解释：整个数组的乘积
(-2) × 3 × (-4) = 24是最大的。
约束：
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都保证是一个 32 位 整数
求解思路
这道题和最大子数组和（LeetCode 53）长得很像，但乘积引入了一个加法没有的麻烦：负数。两个负数相乘会变成正数，这意味着一个当前看起来很小的负数，碰上后面一个负数后可能变成很大的正数。如果只维护以 nums[i] 结尾的最大乘积，遇到负数时会丢掉关键信息。
既然如此，同时维护两个值就行了：以 nums[i] 结尾的子数组乘积的最大值 maxold 和最小值 minold。为什么要维护最小值？因为当前元素如果是负数，它乘以最小值反而可能变成最大值——一个很大的负数乘以一个很小的负数，结果是一个很大的正数。
转移时，新的最大值 maxnew 有三个候选：nums[i] 自己重新开始、maxold * nums[i] 接在之前的最大值后面、minold * nums[i] 接在之前的最小值后面（负负得正）。minnew 同理，取三者中的最小值。最后在整个遍历过程中记录出现过的最大乘积即可。
空间上，每个状态只依赖前一步，两个变量滚动更新就够了。
解法：动态规划
/*
需要维护并不断更新以nums[i]结尾的子数组乘积的最大值和最小值
maxnew = max(nums[i], maxold * nums[i], minold * nums[i])
minnew = min(nums[i], maxold * nums[i], minold * nums[i])
最后返回maxnew
*/
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
int maxold = nums[0];
int minold = nums[0];
int ans = nums[0];
for(int i = 1; i < nums.size(); i++){
int maxnew = max(nums[i], max(maxold * nums[i], minold * nums[i]));
int minnew = min(nums[i], min(maxold * nums[i], minold * nums[i]));
maxold = maxnew;
minold = minnew;
ans = max(ans, maxnew);
}
return ans;
}
};
复杂度： 时间 O(n)，一次遍历；空间 O(1)，只用几个变量。