算法题:乘积最大子序列

题目来源于力扣

理论基础

动态规划

乘积最大子序列

题目描述

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

示例

示例 1:

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

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

解题思路

提前保存最小值,当出现负数,最小值会转化为最大值

Python 解法

def maxProduct(self, nums):

    if nums is None: return 0

    res, curMax, curMin = nums[0], nums[0], nums[0]

    for i in range(1, len(nums)):
        num = nums[i]
        curMax, curMin = curMax * num, curMin * num
        curMin, curMax = min(curMax, curMin, num), max(curMax, curMin, num)

        res = curMax if curMax > res else res
    return res
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!