Maximum Product Subarray
Problem: Maximum Product Subarray
If there are positive numbers only, we can maintain only one number to store current maximum while scanning the array. At each step we can decide whether to start a new product or multiple into previous product. When there are negative numbers, we need to maintain a negative "smallest" product in case that it becomes maximum by multiply another negative number.
Code in Python:
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
res = x = y = nums[0]
for num in nums[1:]:
x, y = max(num, num*x, num*y), min(num, num*x, num*y)
res = max(res, x)
return res