[Python知识库]leetcode152.乘积最大子数组 Python

题目：

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

示例：

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

思路：

动态规划

因为数组中有负数，一个最小的负数乘以一个负数有可能得到一个最大值，所以定义两个变量表示遍历到当前位置的最大乘积和最小乘积。

当前位置的最大乘积可以是当前元素本身，可以是前一位置的最大乘积乘以当前数，也可以是前一位置的最小乘积乘以当前数，这三个数中的最大的，同理，当前位置的最小乘积就是这三个数里面最小的，每遍历一个数就更新当前的最大乘积结果，遍历完成，返回结果。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        maxp = minp = 1
        ans = float('-inf')
        for i in range(1,n+1):
            temp = maxp
            maxp = max(maxp*nums[i-1],minp*nums[i-1],nums[i-1])
            minp = min(temp*nums[i-1],minp*nums[i-1],nums[i-1])
            ans = max(ans,maxp)
        return ans