Maximum Product Subarray — Track Min and Max O(n) [Google, Meta, Amazon]

Problem Statement

Find the contiguous subarray with the largest product.

Input: [2,3,-2,4] → 6 (subarray [2,3]) Input: [-2,0,-1] → 0

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(1) space

Intuition

Unlike sum, a very negative number can become very positive if multiplied by another negative. Track both min and max at each position.

cur_max = cur_min = result = nums[0]
for num in nums[1:]:
    candidates = (num, cur_max*num, cur_min*num)
    cur_max, cur_min = max(candidates), min(candidates)
    result = max(result, cur_max)

C++ Solution

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int cur_max=nums[0], cur_min=nums[0], result=nums[0];
        for (int i=1;i<(int)nums.size();i++) {
            int n=nums[i];
            int a=n, b=cur_max*n, c=cur_min*n;
            cur_max=max({a,b,c}); cur_min=min({a,b,c});
            result=max(result,cur_max);
        }
        return result;
    }
};

Java Solution

class Solution {
    public int maxProduct(int[] nums) {
        int curMax=nums[0],curMin=nums[0],result=nums[0];
        for (int i=1;i<nums.length;i++) {
            int n=nums[i];
            int tmp=curMax;
            curMax=Math.max(n,Math.max(tmp*n,curMin*n));
            curMin=Math.min(n,Math.min(tmp*n,curMin*n));
            result=Math.max(result,curMax);
        }
        return result;
    }
}

Python Solution

def maxProduct(nums):
    cur_max = cur_min = result = nums[0]
    for n in nums[1:]:
        candidates = n, cur_max*n, cur_min*n
        cur_max, cur_min = max(candidates), min(candidates)
        result = max(result, cur_max)
    return result

JavaScript Solution

function maxProduct(nums) {
    let curMax=nums[0],curMin=nums[0],result=nums[0];
    for (let i=1;i<nums.length;i++) {
        const n=nums[i], tmp=curMax;
        curMax=Math.max(n,tmp*n,curMin*n);
        curMin=Math.min(n,tmp*n,curMin*n);
        result=Math.max(result,curMax);
    }
    return result;
}