題目描述
給定一個(gè)整數(shù)數(shù)組 nums 查乒，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）羞芍。
示例 1:
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6欠啤。
示例 2:
輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因?yàn)?[-2,-1] 不是子數(shù)組。
解法
在序列中計(jì)算出以任一個(gè)節(jié)點(diǎn)為終結(jié)點(diǎn)的子序列乘積吠昭，取最大值返回即可傲隶。
首先不妨嘗試以 表示第
個(gè)元素為子序列終結(jié)點(diǎn)的最大乘積：
若
饺律，則有推導(dǎo)式
若
，則以上推導(dǎo)式不成立。不妨以
表示第
個(gè)元素為子序列終結(jié)點(diǎn)的最小乘積复濒，則有
因?yàn)樯婕暗? 函數(shù)脖卖，同理可得：
若
若
因?yàn)? 只與
存在遞推關(guān)系畦木，不妨以
表示每個(gè)位置上的最大、最小序列乘積砸泛。
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
