Leetcode 152. 乘积最大子序列

题目描述

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

示例 1:

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

示例 2:

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

解法

在序列中计算出以任一个节点为终结点的子序列乘积，取最大值返回即可。

首先不妨尝试以 表示第 个元素为子序列终结点的最大乘积：

• 若 ，则有推导式

• 若 ，则以上推导式不成立。不妨以 表示第 个元素为子序列终结点的最小乘积，则有

因为涉及到 函数，同理可得：

• 若 ，则有推导式

• 若 ，则有推导式

因为 只与 存在递推关系，不妨以 表示每个位置上的最大、最小序列乘积。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ret,up,down=nums[0],nums[0],nums[0]
        for n in nums[1:]:
            if n>=0:
                up,down=max(up*n,n),min(down*n,n)
            else:
                up,down=max(down*n,n),min(up*n,n)
            ret=max(ret,up)
        return ret