Leetcode152. 连续子数组的最大乘积

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

题解：动态规划

状态转移方程为：dp[i] = max(dp[i - 1] * nums[i], nums[i])

为每一个状态只与前一个状态有关，可以使用「滚动变量」技巧，使用常数个变量完成这道问题

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int preMax = nums[0];
        int preMin = nums[0];
        int curMax;
        int curMin;
        int res = nums[0];
        for(int i = 1; i < nums.length;i++) {
            if(nums[i] >=0){
                curMax = Math.max(nums[i], preMax*nums[i]);
                curMin = Math.min(nums[i], preMin*nums[i]);
            }
            else{
                curMax = Math.max(nums[i], preMin*nums[i]);
                curMin = Math.min(nums[i], preMax*nums[i]);
            }
            res = Math.max(curMax,res);
            preMax = curMax;
            preMin = curMin;
        }
        return res;
 
    }
}