medium +30 pts

Kadane Variant: Maximum Product Subarray

Find the contiguous subarray with the largest product using a Kadane-inspired approach.

Write a function `max_product_subarray(nums)` that takes a list of integers `nums` (may contain positive, negative, and zero values) and returns the largest product that can be obtained by multiplying a contiguous subarray (i.e., a non-empty slice `nums[i:j]` with `0 <= i < j <= len(nums)`). The array length is at least 1. The product may be large, so return it as a Python integer. Your solution should run in O(n) time and O(1) extra space.

Constraints

1 <= len(nums) <= 10^5. Each element is an integer with absolute value <= 10^4. The product of any subarray fits in a Python integer.

Example

>>> max_product_subarray([2, 3, -2, 4])
6
>>> max_product_subarray([-2, 0, -1])
0
>>> max_product_subarray([-2, -3, 4, -1])
24
>>> max_product_subarray([7])
7
30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Track both the maximum and minimum product ending at the current index, because a negative times a negative can become large.
When you see a negative number, swapping the current max and min before multiplying can simplify the update.
If the current number is zero, both the max and min ending here reset to zero (or consider starting fresh).
The answer is the maximum value that the tracked max has ever reached.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.