v9.1.1
Menu

Maximum Product Subarray

mediumPRODynamic ProgrammingMicrosoft DSA

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

Example

Input
2,3,-2,4
Output
6
Reasoning
  • The input nums is a list of integers, here [2,3,−2,4][2, 3, -2, 4]. A subarray is a contiguous, non-empty run, so there are 4⋅52=10\frac{4 \cdot 5}{2} = 10 candidates.
  • Runs left of the negative: [2][2] gives 22, [3][3] gives 33, [2,3][2, 3] gives 66. On the right, [4][4] gives 44.
  • Every run containing −2-2 has one negative factor, so its product is negative: −2-2 alone gives −2-2, then 3×(−2)=−63 \times (-2) = -6, 2×3×(−2)=−122 \times 3 \times (-2) = -12, (−2)×4=−8(-2) \times 4 = -8, 3×(−2)×4=−243 \times (-2) \times 4 = -24, and the whole list gives −48-48.
  • The largest of the 10 products is 66, from [2,3][2, 3], so the output is the integer 6.
  • Notice that a second negative can rejoin the split: in [−2,3,−4][-2, 3, -4] the signs cancel, giving (−2)×3×(−4)=24(-2) \times 3 \times (-4) = 24. A zero cuts every run through it, so [−2,0,−1][-2, 0, -1] gives 00.

Constraints

  • 1 <= len(nums) <= 2 * 10^4
  • -10 <= nums[i] <= 10

More from Microsoft DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.