Maximum Product Subarray

Problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

A subarray is a contiguous non-empty sequence of elements within an array.

You can assume the output will fit into a 32-bit integer.

Note that the product of an array with a single element is the value of that element.

Examples

Example 1:

Input: nums = [2,4,-3,5]

Output: 8

Explanation: [2,4] has the largest product 8.

Example 2:

Input: nums = [-3,0,-2]

Output: 0

Explanation: The result cannot be 6, because [-3,-2] is not a subarray.

Constraints

• 1 <= nums.length <= 1000
• -10 <= nums[i] <= 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

At every iteration, we track the current best at the index. Any subarray ending at index i has three possibilities:

• Start fresh at the num
• Extend the previous max-product subarray
• Extend the previous min-product subarray (useful if num < 0, turning the min into a max)

class Solution {
public:
    int maxProduct(const vector<int>& nums) {
        auto res = nums[0];
        int cur_max = 1;
        int cur_min = 1;
        for (const auto &num : nums) {
            int old_max = cur_max;
            int old_min = cur_min;
 
            // Invariant after this update:
            // cur_max is the maximum product of any subarray ending at num.
            cur_max = std::max({
                num,              // start new subarray here
                num * old_max,    // extend previous max
                num * old_min     // extend previous min; useful if num < 0
            });
 
            // Invariant after this update:
            // cur_min is the minimum product of any subarray ending at num.
            cur_min = std::min({
                num,              // start new subarray here
                num * old_max,    // extend previous max
                num * old_min     // extend previous min
            });
 
            // Invariant after this update:
            // res is the maximum product of any subarray in the prefix processed so far.
            res = std::max(res, cur_max);
        }
        return res;
    }
};