Maximum Product Subarray

Problem

Find the contiguous subarray with the largest product (not sum) within an array that can contain negative numbers.

Input:  nums = [2, 3, -2, 4]
Output: 6   (subarray [2, 3])

Python Solution

def max_product_subarray(nums):
    max_so_far = min_so_far = result = nums[0]
    for num in nums[1:]:
        if num < 0:
            max_so_far, min_so_far = min_so_far, max_so_far
        max_so_far = max(num, max_so_far * num)
        min_so_far = min(num, min_so_far * num)
        result = max(result, max_so_far)
    return result

C++ Solution

int maxProductSubarray(vector<int>& nums) {
    int maxSoFar = nums[0], minSoFar = nums[0], result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        int num = nums[i];
        if (num < 0) swap(maxSoFar, minSoFar);
        maxSoFar = max(num, maxSoFar * num);
        minSoFar = min(num, minSoFar * num);
        result = max(result, maxSoFar);
    }
    return result;
}

Java Solution

class Solution {
    public int maxProductSubarray(int[] nums) {
        int maxSoFar = nums[0], minSoFar = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num < 0) {
                int temp = maxSoFar; maxSoFar = minSoFar; minSoFar = temp;
            }
            maxSoFar = Math.max(num, maxSoFar * num);
            minSoFar = Math.min(num, minSoFar * num);
            result = Math.max(result, maxSoFar);
        }
        return result;
    }
}

Complexity

Time: O(n) — a single pass, updating two running values per element. Space: O(1) — a running maximum and minimum product are kept, since a negative number can flip a very small (negative) product into the new largest one.