Leetcode 152. 乘积最大子序列

题目描述

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

示例 1:

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

示例 2:

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

解法

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

首先不妨尝试以

up(i)

表示第

i

个元素为子序列终结点的最大乘积：

• 若

nums[i] \ge 0

，则有推导式

up(i)=max[up(i-1)*nums[i], nums[i]]

• 若

nums[i] < 0

，则以上推导式不成立。不妨以

down(i)

表示第

i

个元素为子序列终结点的最小乘积，则有

up(i)=max[down(i-1)*nums[i], nums[i]]

因为涉及到

down(i)

函数，同理可得：

• 若

nums[i] \ge 0

，则有推导式

down(i)=min[down(i-1)*nums[i], nums[i]]

• 若

nums[i] < 0

，则有推导式

down(i)=min[up(i-1)*nums[i], nums[i]]

因为

up(i),down(i)

只与

up(i-1),down(i-1)

存在递推关系，不妨以

up,down

表示每个位置上的最大、最小序列乘积。

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