LeetCode 152. Maximum Product Subarray

[Woodyiiiiiii]

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

---

这道题我首先想到的是动态规划，根据之前Maximum Subarray的思路一样，dp[i]表示以nums[i]为结尾的最大子数组数值之和。主要问题是如何解决负数，因为负数乘以负数是正数，有可能成为最大子集数值之和，但因为之前没有存储负数的可能性，所以会出错。我能想到的就是当nums[i]是负数时，遍历nums数组之前的值，暴力搜索找到最大值。

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > 0) {
                dp[i] = (nums[i] > dp[i - 1]) ? Math.max(dp[i - 1] * nums[i], nums[i])
                    : nums[i] * dp[i - 1];   
            }
            else {
                int t = nums[i], max = Integer.MIN_VALUE;
                for (int j = i - 1; j >= 0; --j) {
                    t *= nums[j];
                    max = Math.max(max, t);
                }
                dp[i] = max;
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

这种做法的时间复杂度最坏情况是O(n^2)，事实上几乎都是最坏情况:)。而且空间复杂度不能继续优化为O(1)。

看了discussion板块，其他人的主要思路是存储之前包含负数的情况——存储最小值，换取时间复杂度为O(n)。因为当前最小值一定包含了负数出现的情况(如果之前出现了负数)，那么碰到第二个负数时最小值与之相乘就可能出现最大值了。

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], preMax = max, preMin = min;
        int ans = nums[0];
        for(int i = 1; i < nums.length; ++i){
            if(nums[i] > 0){
                max = Math.max(nums[i], preMax * nums[i]);
                min = Math.min(nums[i], preMin * nums[i]);
            }else{
                max = Math.max(nums[i], preMin * nums[i]);
                min = Math.min(nums[i], preMax * nums[i]);
            }
            preMax = max;
            preMin = min;
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

---

类似题目：

• 53. Maximum Subarray

参考资料：

• https://leetcode.com/problems/maximum-product-subarray/
• https://leetcode.com/problems/maximum-product-subarray/discuss/580658/Beats-97-Java-or-Easy-dp-Solution