max-product-subarray

Maximum Product Subarray

Inspiration: Kadane’s Algorithm and max-subarray problem. The caveat here is we must maintain both cur_max and cur_min, as negative numbers multiply to be positive.

result = cur_max = cur_min = nums[0]
 
for num in nums[1:]:
    cur_max, cur_min = (
        max(num, cur_max * num, cur_min * num)
        min(num, cur_max * num, cur_min * num)
    )
    result = max(cur_max, result)
 
return result