Q152 Maximum Product Subarray

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

最大字段积不同于最大子段和的一点就是，可能前面累积的是最小乘积，结果遇到了一个负值，就变成了最大乘积。因此，我们需要记录前 k-1 个数的局部最大值和局部最小值，然后遇到第 k 个数时，分别相乘，更新局部最大值和局部最小值。同时，还要有一个全局最大值，来记录最大乘积。

这是一个动态规划问题，时间复杂度：O(n)，空间复杂度：O(1)

举例：nums = [2,-2,3,2,-2,0,-2]，此时列表已经遍历了 [2,-2,3,2]，并且记录了 localMax = 6 和 localMin = -24，当遇到下一个数 -2 时，分别与localMax 和 localMin 相乘，得到 -12 和 24，此时应该将 localMax 更新为24，即取 -12, 24 以及当前数 -2 中的较大一个（为什么还要和当前数比？因为比如遍历到 [2,-2]，结果遇到了 3，此时 localMax 应该更新为 3）； localMin 更新为 -12，即取 -12, 24 以及当前数 -2 中的较小一个。同时，将 globalMax 更新为 24。因此，我们只需要遍历一遍列表就可以找到最大子段积。

注意点：

当遇到 0 后， localMax 和 localMin 均会被更新为 0，但是 gloabalMax 还是 48，这也就是说，localMax 和 localMin 只是记录了局部一段的最大值和最小值，而真正的最大值由 gloabalMax 来记录。

Python实现：

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]