152. 乘积最大子数组

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/maximum-product-subarray/
Star
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输出:6解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

法1 动态规划 时间序列型

思路
乍一看，感觉和最大连续和有点像，但是本题有负数。和最大连续和之间的区别在于：
  • 最大连续和：影响dp[i]的只有s[i] 和 dp[i-1] 。之前的非最大值直接抛弃了
  • 但是本体，之前的非最大值并不能抛弃，如果遇到负数可能直接由最小值变最大值。
所以本题在最大连续和的基础上，再增加一个状态，用来记录以s[i]结尾的子数组的最小值，好随时等待翻身。
题解
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp = [[0]*2 for _ in range(len(nums))]
        # dp[i][0] 到当前元素结尾的最大值
        # dp[i][1] 到当前元素为止的最小值

        # 初始化
        dp[0][0], dp[0][1] = nums[0], nums[0]
        # 状态转移
        for i in range(1, len(dp)):
            dp[i][0] = max(dp[i-1][0] * nums[i], 
                            dp[i-1][1] * nums[i],
                            nums[i])
            dp[i][1] = min(dp[i-1][0] * nums[i], 
                            dp[i-1][1] * nums[i],
                            nums[i])

        return max(map(max, dp))
优化：之和前一个时刻的状态有关！
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp = [nums[0], nums[0]]

        res = nums[0]
        for i in range(1, len(nums)):
            a, b = dp[0] * nums[i], dp[1] * nums[i]
            dp = [min(a, b, nums[i]), max(a, b, nums[i])]
            res = max(res, *dp)

        return res