连续子数组的最大乘积

连续子数组的最大乘积_牛客题霸_牛客网

问题简述

输入一个长度为n的整型数组nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。

思路：动态规划

• 由于乘法特性，负数乘以一个最大/小值会变最小/大值；

• 可以定义 dp_mx, dp_mi 分别保存以 nums[i] 结尾的最大乘积和最小乘积；

• 使用 ret 记录历史最大结果；

Python

class Solution:
    def maxProduct(self , nums: List[int]) -> int:
        
        ret = dp_mx = dp_mi = nums[0]
        for x in nums[1:]:
            tmp_mx, tmp_mi = dp_mx, dp_mi
            dp_mx = max(x, tmp_mx * x, tmp_mi * x)
            dp_mi = min(x, tmp_mx * x, tmp_mi * x)
            ret = max(ret, dp_mx)
            
        return ret