Problem_152. Maximum Product Subarray - xwu36/LeetCode GitHub Wiki

Problem:

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.

Algorithm:

if(num < 0) swap(pos_maxSofar, neg_maxSofar);
pos_maxSofar = Math.max(pos_maxSofar * num, num);
neg_maxSofar = Math.min(neg_maxSofar * num, num);
this can handle multiple zeros case. 
if pos_maxSofar == 0 and num > 0, pos_maxSofar = num;
if pos_maxSofar < 0 and num == 0, pos_maxSofar = num, which is 0;

Code:

class Solution {
    public int maxProduct(int[] nums) {
        //neg_maxSofar = Math.min(num, neg_maxSofar);
        //neg_maxSofar = Math.min(neg_maxSofar, num * pos_maxSofar);
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        int pos_maxSofar = 0;
        int neg_maxSofar = 0;
        int max = Integer.MIN_VALUE;
        for(int num : nums){
            if(num < 0){
                int tmp = pos_maxSofar;
                pos_maxSofar = neg_maxSofar;
                neg_maxSofar = tmp;
            }
            pos_maxSofar = Math.max(pos_maxSofar * num, num);
            neg_maxSofar = Math.min(neg_maxSofar * num, num);
            max = Math.max(max, pos_maxSofar);
        }
        return max;
    }
}