打卡群刷题总结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：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。
PPS：还是得日更呀，总结一下总是好的。