152.乘积最大子数组

题目描述

题解

动态规划

之前做过的53题最大子序和与这道题整体思路是一样的, 都是一边遍历这数组, 一边记录当前的最大值, 最后输出.

但是不同点也是难点在于, 因为有负数的存在, 所以最大值与最小值会随时相互转换.

很好理解, 一个数为最大值, 乘上一个负数就会变成最小值, 所以在遍历的过程中还要维护一个最小值.

)

)

public int maxProduct(int[] nums) {
    int max = Integer.MIN_VALUE;
    int cur_max = 1;
    int cur_min = 1;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < 0) {
            int temp = cur_max;
            cur_max = cur_min;
            cur_min = temp;
        }

        cur_max = Math.max(nums[i], nums[i] * cur_max);
        cur_min = Math.min(nums[i], nums[i] * cur_min);
        max = Math.max(max, cur_max);
    }

    return max;
}