image.png

解法

class Solution {
    public int maxProduct(int[] nums) {
        // 和连续子序列和思想类似，只不过因为负号的存在要维护两个数组
        int len = nums.length;
        // 分别代表以i为结尾的连续子数组，对应的最大值和最小值
        int[] maxDp = new int[len];
        int[] minDp = new int[len];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            maxDp[i] = Math.max(minDp[i - 1] * nums[i], Math.max(maxDp[i - 1] * nums[i], nums[i]));
            minDp[i] = Math.min(maxDp[i - 1] * nums[i], Math.min(minDp[i - 1] * nums[i], nums[i]));
        }
        int maxRes = maxDp[0];
        for (int i = 1; i < maxDp.length; i++) {
            maxRes = Math.max(maxDp[i], maxRes);
        }
        return maxRes;
    }
}

dp只依赖于前一个状态，使用滚动数组

class Solution {
    public int maxProduct(int[] nums) {
        // 和连续子序列和思想类似，只不过因为负号的存在要维护两个数组
        int len = nums.length;
        // 分别代表以i为结尾的连续子数组，对应的最大值和最小值
        int maxDp = nums[0];
        int minDp = nums[0];
        int maxRes = maxDp;
        for (int i = 1; i < len; i++) {
            int preMax = maxDp;
            int preMin = minDp;
            maxDp = Math.max(minDp * nums[i], Math.max(preMax * nums[i], nums[i]));
            minDp = Math.min(preMax * nums[i], Math.min(preMin * nums[i], nums[i]));
            maxRes = Math.max(maxRes, maxDp);
        }
        return maxRes;
    }
}