LeetCode220820_85、乘积最大子数组

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

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

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

示例 1:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解一、动态规划，二维动态数组dp[i][1]、dp[i][0]分别维护最大和最小值

class Solution{
    public int maxProduct(int[] nums){
        int len = nums.length;
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        for(int i = 1; i < len; i++){
            if(nums[i] >= 0){
                dp[i][1] = Math.max(dp[i - 1][1] * nums[i], nums[i]);
                dp[i][0] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
            }else{
                dp[i][1] = Math.max(dp[i - 1][0] * nums[i], nums[i]);
                dp[i][0] = Math.min(dp[i - 1][1] * nums[i], nums[i]);
            }
        }
        int res = dp[0][1];
        for(int i = 1; i < len; i++){
            res = Math.max(res, dp[i][1]);
        }
        return res;
    }
}

题解二、使用滚动变量只存储上一步骤的最大最小，计算后求最大，且进行下次运算前进行更新。

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

题解三、数组元素为负时，最大最小交换在求取。

class Solution{
    public int maxProduct(int[] nums){
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int num : nums){
            if(num < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * num, num);
            imin = Math.min(imin * num, num);
            max = Math.max(max, imax);
        }
        return max;
    }
}