[数据结构与算法]LeetCode.152.乘积最大子数组（动态规划）

题目描述：来自LeetCode

思路：正数*正数=正数，正数*负数=负数，负数*负数=正数，所以要分两种情况来讨论

当第i个数是正数时，且前i-1个数乘积是正数 或者 当第i个数是负数，且前i-1个数乘积是负数，以第i个数结尾的乘积最大子数组一定是*第i个数

当第i个数是正数时，且前i-1个数乘积是负数 或者 当第i个数是负数，且前i-1个数乘积是正数数，以第i个数结尾的乘积最大子数组一定是前i-1个数的乘积

故我们需要记录负数的同时也要记录正数，如果第i个数是负数，前面的乘积也是负数，那肯定就会更大，或者第i个数是正数，前面的乘积也是正数，那肯定也会更大?。我们每次记录并更新这个最大值，但如果相反，结果肯定更小，我们更新这个最小的数，下次再遇到负数，他们相乘一定更大

代码实现C++:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxF=nums[0],minF=nums[0],res=nums[0];
        for(int i=1;i<nums.size();i++){
            int mx = maxF, mn = minF;//记录前i-1个子数组乘积的最大值和最小值
            maxF=max(mx*nums[i],max(mn*nums[i],nums[i]));//更新最大值
            minF=min(mn*nums[i],min(nums[i],mx*nums[i]));//更新最小值
            res=max(maxF,res);//更新最大
        }
        return res;
    }
};

?今日刷题任务完成~