Maximum Product Subarray — Kadane with Min/Max

Problem

Find the subarray with maximum product.

Example: [2,3,-2,4] → 6 ([2,3])

Approach — Track Min and Max

At each step maintain max_prod and min_prod (most negative, in case next num is negative). Swap them when multiplying by a negative number.

Time: O(n) | Space: O(1)

Solutions

Python

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        best=mx=mn=nums[0]
        for n in nums[1:]:
            if n<0: mx,mn=mn,mx
            mx=max(n,mx*n); mn=min(n,mn*n)
            best=max(best,mx)
        return best

C++

class Solution {
public:
    int maxProduct(vector<int>& nums){
        int mx=nums[0],mn=nums[0],best=nums[0];
        for(int i=1;i<nums.size();i++){
            if(nums[i]<0) swap(mx,mn);
            mx=max(nums[i],mx*nums[i]); mn=min(nums[i],mn*nums[i]);
            best=max(best,mx);
        }
        return best;
    }
};

Java

class Solution {
    public int maxProduct(int[] nums){
        int mx=nums[0],mn=nums[0],best=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]<0){int t=mx;mx=mn;mn=t;}
            mx=Math.max(nums[i],mx*nums[i]); mn=Math.min(nums[i],mn*nums[i]);
            best=Math.max(best,mx);
        }
        return best;
    }
}

Complexity

Time: O(n) | Space: O(1)