152. Maximum Product Subarray

从数组（至少包含一个数字）中找出一个连续的子数组，该子数组的乘积最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 6 star, 没做出来
        # 从第二个开始，每次记录最大值和最小值，因为最小值乘以一个负数也可能是最大值
        _max = small = big =  nums[0]
        for i in nums[1:]:
            # small和big的递推公式
            small, big = min(i, i*big, i*small), max(i, i*big, i*small)
            _max = max(_max, big)
        return _max