mediumDynamic Programming 1DPure DSA~28 min
Maximum Product Metric Streak
A stream of multiplicative growth factors (some negative, representing dips) is logged per interval. Find the contiguous streak whose product is largest — the strongest compounding run.
Problem
Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return that product. The answer fits in a 32-bit integer.
Input
An integer array nums of length [1, 2*10^4]; values in [-10, 10].
Output
An integer: the maximum subarray product.
Constraints
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix fits in a 32-bit integer.
Examples
Example 1
Input
nums = [2,3,-2,4]
Output
6
[2,3] gives 6; the -2 would flip the sign.
Example 2
Input
nums = [-2,0,-1]
Output
0
Best contiguous product is 0.