Largest Product Subarray
Problem
A growth model stores daily multipliers as integers, some negative and some zero. Given a non-empty list nums, return the largest product of any non-empty contiguous run of values. The list has up to 20,000 values between -10 and 10, and the answer fits in a normal integer. Checking every run is too slow.
Examples
Input: nums = [2, 3, -2, 4]
Output: 6
Why: the run [2, 3]; adding -2 flips the signInput: nums = [-2, 3, -4]
Output: 24
Why: two negatives cancel, so the whole list winsInput: nums = [-2, 0, -1]
Output: 0
Why: edge case, a zero beats every run that holds a single negativeHints
0 / 3
Kadane's algorithm keeps the best sum of a run ending at each index. Why does keeping only the best product ending here fail on [-2, 3, -4]?
A negative value turns the smallest product into the largest one. So the smallest product ending here is worth keeping too.
Track both the largest and the smallest product of a run ending at the current value. The new pair comes from the value alone, value times the old largest, and value times the old smallest. Update the answer from the largest each step.
Solution
This is Kadane's algorithm with one extra number. For sums, the best run ending here either extends the previous best or starts fresh. For products a very negative run can become the best as soon as another negative arrives, so both the largest and the smallest product of a run ending at the current value are carried forward. Each new value picks its new extremes from three candidates: itself alone, times the old largest, or times the old smallest. A zero resets both to zero, and the next value starts a fresh run through the itself-alone candidate. Time is O(n), and extra space is O(1).
def largest_product(nums):
hi = lo = best = nums[0]
for x in nums[1:]:
candidates = (x, x * hi, x * lo) # start fresh, or extend either extreme
hi, lo = max(candidates), min(candidates)
best = max(best, hi)
return best
print(largest_product([2, 3, -2, 4])) # -> 6
print(largest_product([-2, 3, -4])) # -> 24
print(largest_product([-2, 0, -1])) # -> 0Stuck on the idea rather than the code? Kadane's Algorithm covers it.