📃 题目描述

题目链接：152. 乘积最大子数组 (opens new window)

🔔 解题思路

按照 53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 这题的思路去做的话，即 dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])，这样会出现问题！

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
		
        // nums[i] 左边的最大乘积
        int[] maxDp = new int[nums.length];
        // nums[i] 左边的最小乘积
        int[] minDp = new int[nums.length];

        // base case
        maxDp[0] = nums[0];
        minDp[0] = nums[0];

        int res = maxDp[0];

        for (int i = 1; i < nums.length; i ++) {
            maxDp[i] = Math.max(Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            minDp[i] = Math.min(Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            res = Math.max(maxDp[i], res);
        }

        return res;
    }
}

状态压缩：

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
		
        // nums[i] 左边的最大乘积
        int preMax = nums[0];
        // nums[i] 左边的最小乘积
        int preMin = nums[0];

        int res = nums[0];

        for (int i = 1; i < nums.length; i ++) {
            int curMax = Math.max(Math.max(preMax * nums[i], preMin * nums[i]), nums[i]);
            int curMin = Math.min(Math.min(preMax * nums[i], preMin * nums[i]), nums[i]);

            res = Math.max(res, curMax);
            
            preMax = curMax;
            preMin = curMin;
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：