3.【数组】最大乘积子序列

题目链接：https://leetcode-cn.com/problems/maximum-product-subarray/
描述：
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路：该题目和连续子序列的最大和类似。连续子序列的最大和只需要看前面记录的最大值s对后面的加和有没有增益的贡献。而本题，需要不仅要看每一轮的最大值，还要看每一轮的最小值。

1. 遍历数组时计算当前最大值，不断更新
2. 令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
3. 由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
4. 当负数出现时则imax与imin进行交换再进行下一步计算

时间复杂度为O(n)
具体代码：

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == None or len(nums) == 0:
            return None
        imax = imin = res = nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0:
                imax, imin = imin, imax
            imax = max(nums[i], imax * nums[i])
            imin = min(nums[i], imin * nums[i])
            res = max(res, imax)
        return res