Back to ArraysMaximum Product Subarray
Medium

Maximum Product Subarray

MediumMust DoKadane's Algorithm

Given an array of integers, find the contiguous subarray with the largest product and return that product.

Examples

Example 1

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

Explanation: The subarray [2,3] has the largest product, 6 — extending it to include -2 or -2,4 would lower the product.

Example 2

Input:
nums = [-2,0,-1]
Output:
0

Explanation: Any subarray touching both negative numbers is blocked by the 0 between them, so the best available product is 0.

Example 3

Input:
nums = [-2,3,-4]
Output:
24

Explanation: The whole array's product is (-2) * 3 * (-4) = 24 — the two negative signs cancel out, which is exactly why a running minimum must be tracked alongside the maximum.

Constraints

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

Loading editor…

Code execution is coming soon.