题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

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

示例 2:

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

解题思路

与前面最大和的连续子数组不太一样，这里由于存在负负得正的情况，所以还需要保存一个当前以下标i结尾数组的乘积最小结果。
假设数组为a，fmin(i)表示以下标i结尾数组的最小乘积结果，fmax(i)表示下标i结尾数组的最大乘积结果，递推公式如下：

fmax(i) = max(fmax(i-1)*ai, fmax(i-1)*ai, ai)
fmin(i) = min(fmin(i-1)*ai, fmin(i-1)*ai, ai)

代码如下：

int MaxProduct(vector<int>& nums){
    vector<int> minF(nums), maxF(nums);
    for(int i=1; i<nums.size(); i++){
        maxF[i] = max(maxF[i-1]*nums[i], max(nums[i], minF[i-1]*nums[i]));
        minF[i] = min(minF[i-1]*nums[i], min(nums[i], maxF[i-1]*nums[i]));
    }
    return *max_element(maxF.begin(), maxF.end());
}

// 另外可以不用设置两个数组，直接两个整型变量就可以满足上面迭代要求.