152_乘积最大子数组

类型：数组

• 152. 乘积最大子数组 💛

  https://leetcode-cn.com/problems/maximum-product-subarray/

  ❓ 从整数数组 nums 中找出乘积最大的连续子数组，返回这个最大的乘积。

  💡 动态规划

  我们考虑以第 i 个数为结尾的子数组乘积。对于第 i 个数来说，它有可能加入前面的子数组，也有可能独立成段。由于第 i 个数可能是正数或负数，对于负数来说，我们希望前面的子数组乘积尽可能「负得更多」，即越小越好。对于正数来说，我们希望前面子数组的乘积越大越好。

  因此我们需要同时维护以第 i 个数为结尾的子数组最大乘积和最小乘积。

  class Solution:
      def maxProduct(self, nums: List[int]) -> int:
          dp = [[0, 0] for _ in range(len(nums))]
          dp[0] = [nums[0], nums[0]]
          for i in range(1, len(nums)):
              dp[i] = [
                      min(nums[i], nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1]),
                      max(nums[i], nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1])
                  ]
          max_prod = nums[0]
          for row in dp:
             max_prod = max(max_prod, max(row))
          return max_prod

  时间复杂度：O(n)，空间复杂度：O(1)