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.

Solution:

The continuous element does not need to be adjacent.

For example, [-2, 2, -5] outputs 10, which is - 2 x 5.

At each step, we keep the max and min of the product.

The reason to keep min is because min could be a negative number and negative times negative is positive, which might be a max.

The max at this step is the maximum of max * nums[i], min * nums[i], and nums[i].

The time complexity is O(n) and the space complexity is O(1).



Code:

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = 1;
        int min = 1;
        int result = nums[0];
        for (int num : nums) {
            int tmp = max;
            max = Math.max(num, Math.max(num * max, num * min));
            min = Math.min(num, Math.min(num * tmp, num * min));
            result = Math.max(result, max);
        }
        return result;
    }
}