力扣_动态规划2—乘积最大的子数组

题目

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

对比：“力扣_数组19—最大子数组和”

方法—动态规划

• 类似“力扣_数组19—最大子数组和”的方法
  • 以第 $i$ 个元素结尾的子数组的最大乘积 $f(i)=max(f(i-1)\ast nums[i],nums[i])$
  • 但这样是不对的，假如 $f(i-2)$ 为负，$nums[i]$ 为负，$nums[i-1]$ 为正，这种情况下得到的 $f(i)=nums[i]$，但应该为 $f(i)=f(i-2)\ast nums[i-1]\ast nums[i]$
• 改进
  • 若 $nums[i]$ 为负，则 $f_{max}(i)=max(f_{min}(i-1)\ast nums[i],nums[i])$
  • 若 $nums[i]$ 为正，则 $f_{max}(i)=max(f_{max}(i-1)\ast nums[i],nums[i])$
  • 综上，$f_{max}(i)=max(f_{max}(i-1)\ast nums[i],f_{min}(i-1)\ast nums[i],nums[i])$
  • 因此，每次循环需要更新 $f_{max},f_{min}$

代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int dp_max = nums[0];
        int dp_min = nums[0];
        int ret = nums[0];
        for(int i = 1; i < n; i++){
            int temp_max = dp_max;
            int temp_min = dp_min;
            dp_max = max(nums[i], max(temp_max*nums[i], temp_min*nums[i]));
            dp_min = min(nums[i], min(temp_max*nums[i], temp_min*nums[i]));
            ret = max(ret, dp_max);
        }
        return ret;
    }
};