LeetCode 152.乘积最大子数组

题目(10¥)

题目地址:https://leetcode-cn.com/problems/maximum-product-subarray/

题解

动态规划题,这一题要注意区分两种情况,数的正负。
原本我们只需要一个的dp数组,这边需要两个,记录最优解(目前位置最大值,目前位置最小值)。
当前数为正数时,状态转移方程:

dpMax[i] = Math.max(dpMax[i - 1] * nums[i], nums[i])

当前数为负数时,状态转移方程:

dpMin[i] = Math.min(dpMin[i - 1] * nums[i], nums[i])

因为我们计算 dp[i] 的时候只关注 dp[i - 1] 所以可以简化空间复杂度到 O(1)。

源码
class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] < 0) {
                int tmp = imax;
                imax = imin;
                imin = tmp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(max,imax);
        }
        return max;
    }
}
上一篇:LeetCode313. Super Ugly Number


下一篇:2021-10-28