Description
Find the largest product of a nonempty contiguous subarray. Input guarantees relevant products fit signed 32-bit integers.
Solution
def max_product(nums):
low = high = best = nums[0]
for i in range(1, len(nums)):
value = nums[i]
a,b = low*value,high*value
low,high = min(value,a,b),max(value,a,b)
best = max(best,high)
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[-2,3,-4]]- Output
24
The whole array multiplies to 24.
Example 2
- Input
[[0,-2,0]]- Output
0
A zero beats every negative candidate.
Example 3
- Input
[[-3]]- Output
-3
The only nonempty subarray has product -3.
Approach
Track both maximum and minimum ending products because multiplication by a negative swaps their roles.
Time & space
O(n) time; O(1) space. Here n is the input length.