152. 乘积最大子序列

题目描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

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

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

知识点

动态规划

Qiang的思路

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mi=[nums[0]]
        ma=[nums[0]]
        for i in range(1, len(nums)):
            if nums[i]==0:
                mi.append(0)
                ma.append(0)
            elif nums[i]>0:
                mi.append(min(mi[i-1]*nums[i], nums[i]))
                ma.append(max(ma[i-1]*nums[i], nums[i]))
            else:
                mi.append(min(ma[i-1]*nums[i], nums[i]))
                ma.append(max(mi[i-1]*nums[i], nums[i]))
        return max(ma)

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。