Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
👉 If all the numbers are positive the product is always increasing. But when it comes to negative numbers, It gets alot more tricky as the product of two negatives, is a positive. When we have a vector of all negatives, the signs of the product will be alternating. eg. {-1,-2,-3,-4,-5} => -1, 2, -6, 24, -120
so, to find maximum in such case, we need to track both maximum and minimum. example, in {-1,-2,-3} max of first two elements will be 2 and min will be -2 but when combined with the third element -3, our min will become -2*-3 = 6 which is our desired answer. I hope the reason of storing minimum is pretty clear now.
def maxProduct(self, nums: List[int]) -> int:
local_max, local_min, global_max = nums[0], nums[0], nums[0]
for num in nums[1:]:
temp = local_max
local_max = max(num, num*local_max, num*local_min)
local_min = min(num, num*temp, num*local_min)
global_max = max(local_max, global_max)
return global_max