152. Maximum Product Subarray

Description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Idea

Keep track the max and the min, and every time we meet a negative number, swap max and min. Finally, we will get the result.

Solution

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