Given an array of integers, the machine must find the contiguous subarray whose product is largest. Unlike the maximum subarray sum, the answer cannot be derived from a single running value, because a negative times a negative turns small into large.
The key insight is sign asymmetry: the best product ending at the current position can come from either the largest or the smallest previous product, depending on whether the current element is negative. Multiplying a negative flips the ordering, so the machine must track both the running maximum and the running minimum.
The approach runs in three steps. First, seed all three tracking values — best, running max, and running min — with the first element. Second, for each remaining element, swap the running max and min if the element is negative, then update both as the element itself or the element times the previous running value. Third, keep the largest running max ever seen. Time is O(n) and space is O(1).
The trickiest edge case is zero: a zero resets both running values to 0, which is correct because any subarray spanning it has product 0, and the best-so-far still holds the pre-zero answer. A subtler case is an even count of negatives separated by zeros, which forces the machine to reconsider subarrays that skip the zero entirely.
def maxProduct(nums):
best = cur_min = cur_max = nums[0]
for x in nums[1:]:
if x < 0:
cur_min, cur_max = cur_max, cur_min
cur_max = max(x, cur_max * x)
cur_min = min(x, cur_min * x)
best = max(best, cur_max)
return best