长大后想做什么？做回小孩！

0%

LeetCode——乘积最大子数组

发表于 分类于 Valine：
本文字数： 203

NO.152 乘积最大子数组 中等

YPO85F.png

思路一：动态规划 不能立刻舍弃小于当前的值，因为最小的值可能会在后面乘上另一个负数后变成最大的数，而最大的数也可能乘上一个负数变成最小的数。

所以，DP 的过程中需要记录当前位置 i 为结尾的子数组的最大乘积 imax 和最小乘积 imin，当遇到 nums[i] 是负数的时候， imax 和 imin 的角色发生互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxProduct(int[] nums) {
    int imax = 1, imin = 1;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        //当前元素是负数,imax imin 互换
        if (nums[i] < 0) {
            int temp = imax;
            imax = imin;
            imin = temp;
        }
        //分别记录乘积最大子数组的值 和 乘积最小子数组的值
        imax = Math.max(imax * nums[i], nums[i]);
        imin = Math.min(imin * nums[i], nums[i]);
        //更新 max
        max = Math.max(max, imax);
    }
    return max;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github