The problem
Given an integer array nums, return the largest product of any subarray — a run of one or more consecutive elements.
Examples
01
- Input
nums = [2, 3, -2, 4]
- Output
6
02
- Input
nums = [-2, 0, -1]
- Output
0
Constraints
- 1 ≤ nums.length ≤ 2 × 10⁴
- −10 ≤ nums[i] ≤ 10
- Every product of a prefix or suffix fits in a 32-bit integer.
The idea
For sums, the best run ending here is the best run ending just before, extended — or a fresh start. Products add a twist: multiplying by a negative number turns the largest product into the smallest and the smallest (most negative) into the largest.
So keep both: hi and lo, the largest and smallest products of a run ending at the current element. The new ones are the largest and smallest of: the element alone, hi × x, and lo × x. The answer is the largest hi seen. For [2, 3, −2, 4]: hi goes 2, 6, −2, 4 and lo 2, 3, −12, −48; the best is 6.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def maxProduct(self, nums: List[int]) -> int: # Track the largest and the smallest product of a run ending here: a negative number # turns the smallest (most negative) into the largest. hi = lo = best = nums[0] for x in nums[1:]: hi, lo = max(x, hi * x, lo * x), min(x, hi * x, lo * x) best = max(best, hi) return best