Maximum Product Subarray

medium

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

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

Test Cases

Copy an input into the main harness and Run to verify

Input

nums = [2,3,-2,4]

Expected Output

6

Explanation: The subarray [2,3] has the largest product 6.

Input

nums = [-2,0,-1]

Expected Output

0

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

Hint 1 — click to reveal

Unlike sums, a very negative product is valuable — one more negative number flips it to a large positive.

Hint 2 — click to reveal

Track the running maximum *and* the running minimum at every index.

Java Compiler