140. Maximum Product Subarray
Choose one uninterrupted range of array positions and multiply all of its values. Return the largest product obtainable from any nonempty range.
A negative value can turn a negative product into a positive one, and zero can separate useful ranges. Do not confuse this objective with maximum subarray sum.
Example 1
Input
nums=[2,3,-2,4]
Output
6
Explanation: The interval [2,3] beats every interval including the later negative.
Example 2
Input
nums=[-2,3,-4]
Output
24
Explanation: The minimum product ending before −4 is −6; multiplying it by −4 creates the maximum 24.
Example 3
Input
nums=[-2,0,-1]
Output
0
Explanation: The two negatives cannot be combined across the separating zero.
Example 4
Input
nums=[-2147483648,-1]
Output
2147483648
Explanation: The exact product exceeds int and must not wrap.
Constraints
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Hints
Hint 1
A contiguous interval ending here either starts here or extends one ending immediately before.
Hint 2
Which previous extreme becomes useful when the current value is negative?
Hint 3
Compare x, oldMaximum×x, and oldMinimum×x for both new extremes, then update a separate global best.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A previous minimum becomes the next maximum
[-2,3,-4]
"24"