61. 乘积最大子数组.md

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

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

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #由于存在负数，那么会导致最大的变最小的，最小的变最大的，因此需要维护 dp_max[i] 即以位置 i 结尾的当前最大乘积， dp_min[i] 以位置 i 结尾的当前最小乘积。
        n = len(nums)
        dp_max = [0]*n
        dp_min = [0]*n
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]
        res = max(dp_max[0], dp_min[0])
        for i in range(1,n):
            dp_max[i] = max(nums[i], dp_max[i-1]*nums[i], dp_min[i-1]*nums[i])
            dp_min[i] = min(nums[i], dp_min[i-1]*nums[i], dp_max[i-1]*nums[i])
            res = max(res, dp_max[i], dp_min[i])
        return res