Maximum Product Subarray

Medium Arrays & Hashing Kadane's Algorithm Original on LeetCode

Maximum Product Subarray is a medium arrays & hashing problem solved with the kadane's algorithm pattern. The best approach, optimal (track max and min product ending here), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every subarray) up.

Problem

Given an integer array nums, find the non-empty contiguous subarray whose elements have the largest product, and return that product.

Negative numbers matter here: two negatives multiply to a positive, so the best subarray may contain negative values, and a single 0 cuts every product that crosses it.

Examples

Example 1

Input
nums = [3, -1, 4, 2, -5]
Output
120
Why
The whole array has two negatives, so its product 3 · (-1) · 4 · 2 · (-5) = 120 is positive and the largest.

Example 2

Input
nums = [-4, 0, -3]
Output
0
Why
Every non-empty subarray that avoids 0 is a single negative number, so 0 itself is best.

Example 3

Input
nums = [-2, 5, -3, 0, 6]
Output
30
Why
The subarray [-2, 5, -3] multiplies to 30, beating [6].

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • The product of every subarray fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (every subarray)O(n²)O(1)
Optimal (track max and min product ending here)O(n)O(1)

1Brute force (every subarray)

TimeO(n²)There are n(n + 1) / 2 subarrays and each extension costs O(1).
SpaceO(1)A running product and the best value.

Fix a start index, extend the end one step at a time while keeping the running product, and remember the largest product seen.

  1. best = nums[0].
  2. For each start i: prod = 1; for each end j >= i: prod *= nums[j]; best = max(best, prod).
  3. Return best.
class Solution {
    public int maxProduct(int[] nums) {
        int best = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int prod = 1;
            for (int j = i; j < nums.length; j++) {
                prod *= nums[j];
                best = Math.max(best, prod);
            }
        }
        return best;
    }
}

2Optimal (track max and min product ending here)

TimeO(n)One pass with constant work per element.
SpaceO(1)Three running values.

A Kadane-style scan that keeps two values: the largest and the smallest product of a subarray ending at the current index. Multiplying by a negative number swaps their roles, and a zero resets both, so the new extremes always come from x, x · oldMax or x · oldMin.

  1. hi = lo = best = nums[0].
  2. For each next x: candidates are x, x · hi and x · lo.
  3. hi = max of the candidates, lo = min of the candidates (computed from the old values).
  4. best = max(best, hi). Return best.
class Solution {
    public int maxProduct(int[] nums) {
        int hi = nums[0], lo = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int a = x * hi, b = x * lo;
            hi = Math.max(x, Math.max(a, b));
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }
}

Edge cases to test

  • A single negative number: the answer is that negative number
  • Zeros split the array into independent pieces
  • An odd number of negatives: one of them has to be left out
  • All values negative

Hints

Hint 1

With sums, Kadane's algorithm keeps the best sum ending at each index. Why does that alone fail for products?

Hint 2

A very negative product can turn into the largest one after one more negative factor.

Hint 3

Track both the largest and the smallest product of a subarray ending at index i. The next value multiplies either one, or starts fresh.

FAQ

What is the best time complexity for Maximum Product Subarray?

Optimal (track max and min product ending here) runs in O(n) time and O(1) extra space. One pass with constant work per element.

Which pattern does Maximum Product Subarray use?

It is a arrays & hashing problem that uses the kadane's algorithm pattern. Other problems with the same pattern: Kadane's Algorithm - Simple, Find minimum subarray sum, Kadane's Algo - Circular Array - No Extra Space.

Is there a brute force solution for Maximum Product Subarray?

Yes. Brute force (every subarray) takes O(n²) time and O(1) space. Fix a start index, extend the end one step at a time while keeping the running product, and remember the largest product seen.

Which edge cases should I test for Maximum Product Subarray?

A single negative number: the answer is that negative number; Zeros split the array into independent pieces; An odd number of negatives: one of them has to be left out; All values negative.