Maximum Product Subarray
Medium · dynamic programming
Given a list of integers nums, look at every contiguous block of one or more items and multiply the items in the block together. Return the largest product you can get.
The block must contain at least one number, so a list with a single item simply returns that item, even when it is negative or zero.
Examples
Example 1
Input: nums = [2, 3, -2, 4]
Output: 6
The block [2, 3] gives 6. Including -2 would turn the product negative.
Example 2
Input: nums = [-2, 3, -4]
Output: 24
Two negative numbers cancel out, so the whole list gives -2 * 3 * -4 = 24.
Example 3
Input: nums = [-3, 0, -1]
Output: 0
A block that holds the 0 gives 0, and the single items -3 and -1 are both worse.
Constraints
- 1 <= len(nums) <= 3000
- -10 <= nums[i] <= 10
- The product of every contiguous block fits in a 32-bit signed integer.