711. Best Product Stretch
A trading game gives you a row of multipliers nums, which can be positive, negative or zero. You must pick one stretch of one or more consecutive multipliers and multiply them together; your score is the product. A negative multiplier can flip a very bad stretch into a very good one, and a zero wipes a stretch out.
Return the largest score any stretch can reach. Products may grow huge, so if the best score is larger than 1000000000 return 1000000000 instead.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- nums = [2,-5,-2,-4,3]
- Output:
- 24
- Explanation:
The stretch -2, -4, 3 has product 24; the longer stretches that include -5 end up negative or smaller, so 24 is the best.
Example 2
- Input:
- nums = [-4,0,-6]
- Output:
- 0
- Explanation:
Stretches containing the 0 score 0, and the single values -4 and -6 are negative, so the best score is 0.
Example 3
- Input:
- nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
- Output:
- 1000000000
- Explanation:
All 31 twos together give 2^31, which is above the cap, so the answer is 1000000000.
Constraints
1 ≤ n = nums.length ≤ 105
-10 ≤ nums[i] ≤ 10
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)