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.

Test cases:

[1,-1,7,-4,-9,10]
[1,2,3]
[-1,-2,-3]
[-2,-3,-4,-5,-6]

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int result = nums[0];
        int curMax = nums[0];
        int curMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // curMax and curMin will change after first curMax statement,
            // so should use max/min parameters to maintain original value.
            int max = curMax;
            int min = curMin;
            curMax = Math.max(nums[i],
                            Math.max(nums[i] * max, 
                                     nums[i] * min));
            curMin = Math.min(nums[i],
                            Math.min(nums[i] * max, 
                                     nums[i] * min));
            result = Math.max(result, curMax);
        }
        return result;
    }
}
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