【Check 74】2024-05-15 - 152. 乘积最大子数组

[larscheng]

152. 乘积最大子数组

• 关联 #119

[larscheng]

思路

 * [2,3,-2,4]
 * 假设dp[i]表示子数组num[0:i]中连续元素的最大乘积
 * dp[0]=num[0]
 * dp[1]=max(dp[0],dp[0]*num[1])
 * dp[i] = max(num[i],dp[i-1]*num[i])
 *
 * 但num[i]存在负数，如果num[i]为负数，肯定期望dp[i-1]是一个负数，或者是一个足够小的数
 * 所以ep[i]表示子数组num[0:i]中连续元素的最小乘积
 * ep[i] = min(num[i],ep[i-1]*num[i])

可通过滚动变量优化空间复杂度

代码

class Solution {

    public int maxProduct(int[] nums) {
        int[] maxDp = new int[nums.length];
        int[] minDp = new int[nums.length];
        maxDp[0]=nums[0];
        minDp[0]=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]>=0){
                maxDp[i] = Math.max(nums[i],maxDp[i-1]*nums[i]);
                minDp[i] = Math.min(nums[i],minDp[i-1]*nums[i]);
            }else {
                //当前元素为负数，找上一轮最小结果，来计算最大乘积
                maxDp[i] = Math.max(nums[i],minDp[i-1]*nums[i]);
                //当前元素为负数，找上一轮最大结果，来计算最小乘积
                minDp[i] = Math.min(nums[i],maxDp[i-1]*nums[i]);
            }
        }
        int res = maxDp[0];
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(res,maxDp[i]);
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)