Maximum Product Subarray

Medium
20.

Maximum Product Subarray

Maximum Product Subarray is a medium coding problem on arrays and dynamic programming, asked in Morgan Stanley interviews.

Given an integer array nums, find a contiguous non-empty subarray with the largest product and return that product.

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 answer cannot be 2 because [-2,-1] is not contiguous.

Constraints

  • 1 <= nums.length <= 12
  • -5 <= nums[i] <= 5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Product Subarray — Solution in Python, Java & C++

Maximum Product Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Product Subarray is a medium coding problem on arrays and dynamic programming, asked in Morgan Stanley interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Morgan Stanley
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums, find a contiguous non-empty subarray with the largest product and return that product.

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 answer cannot be 2 because [-2,-1] is not contiguous.

Constraints

  • 1 <= nums.length <= 12
  • -5 <= nums[i] <= 5

Hints for Maximum Product Subarray

  1. Hint 1

    A negative number flips the sign — the smallest product so far can become the largest.

  2. Hint 2

    Track both the maximum AND minimum product ending at each position.

How to solve Maximum Product Subarray

Kadane's trick does not transfer directly, because multiplying by a negative number turns the smallest running product into the largest. So carry two values at each position — the maximum and the minimum product ending there — and let a negative element swap their roles.

Approach

  1. Seed both the running maximum and running minimum with the first element, along with the best answer.
  2. For each later element x, form three candidates: x alone, x * runningMax, and x * runningMin.
  3. The new running maximum is the largest of the three; the new running minimum is the smallest.
  4. Compute both from the old values before overwriting either.
  5. Update the global best with the new running maximum.

Why it works

The largest product ending at a position comes either from starting fresh or from extending the previous subarray — and if x is negative, extending the most negative previous product is what produces the largest new one. Tracking the minimum alongside the maximum is exactly what keeps that possibility available. A zero resets both, which is correct: no subarray spanning it can beat starting over.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Compute the new max and min from the old pair — overwriting the max first and then using it for the min is the classic bug.
  • Include x on its own among the candidates, which is what performs the restart after a zero.
  • Seed from nums[0], not 1 or 0; the subarray must be non-empty.
  • Two negatives multiply to a positive, so a long stretch of negatives can be the answer.

Reference solution

Python

from typing import List

def maxProduct(nums: List[int]) -> int:
    best = hi = lo = nums[0]
    for x in nums[1:]:
        cands = (x, hi * x, lo * x)
        hi = max(cands)
        lo = min(cands)
        best = max(best, hi)
    return best

Java

public static int maxProduct(int[] nums) {
    int curMax = nums[0], curMin = nums[0], best = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        int a = x, b = x * curMax, c = x * curMin;
        curMax = Math.max(a, Math.max(b, c));
        curMin = Math.min(a, Math.min(b, c));
        if (curMax > best) best = curMax;
    }
    return best;
}

C++

int maxProduct(vector<int>& nums) {
    int curMax = nums[0], curMin = nums[0], best = nums[0];
    for (int i = 1; i < (int) nums.size(); i++) {
        int x = nums[i];
        int a = x, b = x * curMax, c = x * curMin;
        curMax = max(a, max(b, c));
        curMin = min(a, min(b, c));
        if (curMax > best) best = curMax;
    }
    return best;
}

JavaScript

var maxProduct = function(nums) {
    let best = nums[0], hi = nums[0], lo = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];
        const a = x, b = hi * x, c = lo * x;
        hi = Math.max(a, b, c);
        lo = Math.min(a, b, c);
        best = Math.max(best, hi);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming