152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路: 乘积的最大值可能来自于两个正数相乘或者两个负数相乘。所以我们要同时来保存每次乘积的最大值跟最小值.
复杂度: time O(n), space: O(n)

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] maxProds = new int[nums.length];
        int[] minProds = new int[nums.length];
        int res = nums[0];
        maxProds[0] = minProds[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxProds[i] = Math.max(nums[i], maxProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], minProds[i-1] * nums[i]);
            } else {
                maxProds[i] = Math.max(nums[i], minProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], maxProds[i-1] * nums[i]);
            }
            res = Math.max(maxProds[i], res);
        }
        return res;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s