152. Maximum Product Subarray

Medium

Problem Description

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

The test cases are generated so that the answer will fit in a 32-bit integer.

Examples

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

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def maxProduct(nums: List[int]) -> int:
    if not nums:
        return 0
    
    max_so_far = min_so_far = result = nums[0]
    
    for num in nums[1:]:
        candidates = (num, max_so_far * num, min_so_far * num)
        max_so_far = max(candidates)
        min_so_far = min(candidates)
        result = max(result, max_so_far)
    
    return result

Java Solution


class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
            minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));
            maxSoFar = tempMax;
            
            result = Math.max(result, maxSoFar);
        }
        
        return result;
    }
}

C++ Solution


class Solution {
public:
    int maxProduct(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            int curr = nums[i];
            int tempMax = max({curr, maxSoFar * curr, minSoFar * curr});
            minSoFar = min({curr, maxSoFar * curr, minSoFar * curr});
            maxSoFar = tempMax;
            
            result = max(result, maxSoFar);
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    if (!nums.length) {
        return 0;
    }
    
    let maxSoFar = nums[0];
    let minSoFar = nums[0];
    let result = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        const curr = nums[i];
        const tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
        minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));
        maxSoFar = tempMax;
        
        result = Math.max(result, maxSoFar);
    }
    
    return result;
};

C# Solution


public class Solution {
    public int MaxProduct(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            int curr = nums[i];
            int tempMax = Math.Max(curr, Math.Max(maxSoFar * curr, minSoFar * curr));
            minSoFar = Math.Min(curr, Math.Min(maxSoFar * curr, minSoFar * curr));
            maxSoFar = tempMax;
            
            result = Math.Max(result, maxSoFar);
        }
        
        return result;
    }
}

Complexity Analysis

Solution Explanation

This solution uses dynamic programming with two variables:

Key points: