Largest product of a contiguous run: track the high and the low at each step, because a negative number swaps them.
▼The problem
LeetCode 152 (Medium). Given an integer array nums, return the largest product of a contiguous, non-empty subarray.
Examples (LeetCode's): [2,3,-2,4] → 6 (the piece [2,3]), and [-2,0,-1] → 0 (the zero alone).
The solution
def max_product(nums):
best = hi = lo = nums[0]
for x in nums[1:]:
cands = (x, x * hi, x * lo)
hi, lo = max(cands), min(cands)
best = max(best, hi)
return bestTranscript
Maximum Product Subarray. Given an array of integers, find the contiguous, non-empty piece with the largest product, and return that product.
For two, three, minus two, four, the answer is six: two times three. For minus two, zero, minus one, the best piece is the zero alone, so the answer is zero.
The direct way: try every subarray and multiply. Four numbers make ten subarrays. That's n squared products.
The key idea is Maximum Subarray's Kadane: keep the best product ending at each number. But a negative flips the sign, so the smallest product can become the largest. In minus two, three, minus four, the low is minus six, and minus four turns it into twenty four. So keep both a high and a low. For each x, the new high is the largest of x, x times high, and x times low. The new low is the smallest. A zero resets both.
In code, high, low and best start at the first number. For each next x, build the three candidates. The max becomes high, the min becomes low, and best keeps the largest high.
On two, three, minus two, four, we start at two. Three makes the high six, so best is six. Minus two swaps them: high minus two, low minus twelve. Four makes the high four and the low minus forty eight. Best stays six.
One pass, three running numbers: O of n time and O of one space.
Track the high, track the low, and let negatives swap them. That's Maximum Product Subarray.