Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
解題思路：
先來回顧最大子段和問題：Q53 Maximum Subarray
最大字段積不同于最大子段和的一點(diǎn)就是，可能前面累積的是最小乘積，結(jié)果遇到了一個負(fù)值，就變成了最大乘積。因此，我們需要記錄前 k-1 個數(shù)的局部最大值和局部最小值，然后遇到第 k 個數(shù)時，分別相乘，更新局部最大值和局部最小值。同時，還要有一個全局最大值，來記錄最大乘積。
這是一個動態(tài)規(guī)劃問題，時間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)
舉例：nums = [2,-2,3,2,-2,0,-2]，此時列表已經(jīng)遍歷了 [2,-2,3,2]，并且記錄了 localMax = 6 和 localMin = -24，當(dāng)遇到下一個數(shù) -2 時，分別與localMax 和 localMin 相乘，得到 -12 和 24，此時應(yīng)該將 localMax 更新為24，即取 -12, 24 以及當(dāng)前數(shù) -2 中的較大一個（為什么還要和當(dāng)前數(shù)比？因?yàn)楸热绫闅v到 [2,-2]，結(jié)果遇到了 3，此時 localMax 應(yīng)該更新為 3）； localMin 更新為 -12，即取 -12, 24 以及當(dāng)前數(shù) -2 中的較小一個。同時，將 globalMax 更新為 24。因此，我們只需要遍歷一遍列表就可以找到最大子段積。
注意點(diǎn)：
當(dāng)遇到 0 后， localMax 和 localMin 均會被更新為 0，但是 gloabalMax 還是 48，這也就是說，localMax 和 localMin 只是記錄了局部一段的最大值和最小值，而真正的最大值由 gloabalMax 來記錄。
Python實(shí)現(xiàn)：
class Solution:
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
globalMax = localMax = localMin = nums[0]
for i in range(1, len(nums)):
cur1 = localMax * nums[i]
cur2 = localMin * nums[i]
localMax = max(cur1, cur2, nums[i]) # 更新局部最大值
localMin = min(cur1, cur2, nums[i]) # 更新局部最小值
globalMax = max(globalMax, localMax) # 更新全局最大值
return globalMax
a = [2,-2,3,2,-2,0,-2]
print(Solution().maxProduct(a)) # 48 # [2,-2,3,2,-2]
