Maximum Product Subarray

We face a problem with positive and negative numbers multiplying together. When we encounter a negative number, we want the smallest possible value to multiply it by—since that gives us the largest positive result. When we have a positive number, we want the largest possible value. So we need to track two things: the minimum and maximum products up to the current position.

int maxProduct(vector<int>& nums) {
    int res=nums[0];

    for(int i=1, mi=nums[0], ma=nums[0];i<nums.size();++i) {
        if (nums[i]<0) swap(mi, ma);

        mi = min(nums[i], mi*nums[i]);
        ma = max(nums[i], ma*nums[i]);

        res = max(ma, res);
    }
    return res;
}

The key insight: when we hit a negative number, our min and max swap roles. The previous minimum (most negative) becomes our new maximum when multiplied by the negative number, giving us the largest positive product.

#DP