打卡群刷题总结0918——乘积最大子数组

题目：152. 乘积最大子数组

链接：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] 不是子数组。

解题：

1、dp问题。

遍历数组元素，pos_dp和neg_dp初始值都为1，公式如下：

pos_dp = max(n, pos_dp * n, neg_dp * n)

neg_dp = min(n, pos_dp * n, neg_dp * n)

找到最大的pos_dp，就是满足条件的解。

代码：

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pos_dp = 1
        neg_dp = 1
        res = -sys.maxsize
        for i, n in enumerate(nums):
            pos_dp, neg_dp = max(n, pos_dp * n, neg_dp * n), min(n, pos_dp * n, neg_dp * n)
            if pos_dp > res:
                res = pos_dp
        return res

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。