LeetCode 乘积最大子序列（动态规划）

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

示例 1:

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

示例 2:

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

思路分析：如果这道题数据都是正数，那么大家都会毫不犹豫的使用动态规划，但是现在测试数据中存在负数，在某种情况下，但是出现[-10，20，-32]这种就不好处理了，因为负负得正，可能比正数还大的情况。解决办法，使用两个数组，分别记录以nums[i]作为结尾的最大乘积、最小乘积，然后动态规划更新即可。

class Solution {
public:
	int maxProduct(vector<int>& nums) {
		int numsSize = nums.size();
		vector<int> maxDp = nums;//maxDp[i]用于储存以nums[i]结尾的乘积最大的连续子序列
		vector<int> minDp = nums;//minDp[i]用于储存以nums[i]结尾的乘积最小的连续子序列
		int tempMaxValue, tempMinValue, resultMaxValue = nums[0];
		for (int index = 1; index < numsSize; ++index) {
			tempMaxValue = maxDp[index - 1] * nums[index];//maxDp[index - 1]为以前一个为尾部元素最大乘积
			tempMinValue = minDp[index - 1] * nums[index];//minDp[index - 1]为以前一个为尾部元素最小乘积（可能是正数，负负得正，比上面的乘积还大）
			maxDp[index] = max(max(nums[index], tempMaxValue), tempMinValue);//更新maxDp[index]以index结尾的连续乘积最大值
			minDp[index] = min(min(nums[index], tempMinValue), tempMaxValue);//更新minDp[index]以index结尾的连续乘积最小值
			resultMaxValue = max(resultMaxValue, maxDp[index]);//更新整体最大值
		}
		return resultMaxValue;
	}
};