leetcode热题100.乘积最大子数组（动态规划进阶）

 作者：晓宜🌈🌈🌈

携程javaer，阿里云专家博主，csdn后端优质创作者 ❤️❤️❤️

今天给大家带来一道动态规划的算法题，希望对大家秋招找工作有帮助🍗🍗🍗

题目

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

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组

（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

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

示例 2:

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

思路

我选择使用动态规划的方法来解题。具体而言，我们需要维护两个变量：当前子数组的最大乘积和最小乘积。这是因为负数的存在会使得最大乘积和最小乘积互换，所以在每一步，我们需要考虑当前元素的正负性，更新这两个变量，以便在最终得到全局的最大乘积。

解题过程

1. 初始化三个变量：

   • ans 用来记录最终的最大乘积，初始值设为一个很小的负数（确保它会被第一个元素更新）。
   • minv 和 maxv 分别用来记录到当前元素为止的最小乘积和最大乘积，初始值都设为 1。

2. 遍历数组 nums，对每个元素 nums[i]：

   • 如果 nums[i] 是负数，交换 minv 和 maxv，因为负数会把最大的乘积变成最小的乘积，反之亦然。
   • 更新 maxv 为 max(maxv * nums[i], nums[i])，即当前元素的最大乘积是前一步的最大乘积乘以当前元素或当前元素自身（当当前元素大于前一步的最大乘积乘以当前元素时）。
   • 更新 minv 为 min(minv * nums[i], nums[i])，即当前元素的最小乘积是前一步的最小乘积乘以当前元素或当前元素自身。
   • 更新 ans 为 max(ans, maxv)，即在每一步都更新全局的最大乘积。

3. 最后返回 ans，即为整个数组的最大子数组乘积。

复杂度

• 时间复杂度: O(n)，因为我们只需遍历数组一次。
• 空间复杂度: O(1)，因为我们只使用了常数个额外空间。

Code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        ans = -1000000
        minv = maxv = 1
        for i in range(n):
            if nums[i] < 0:
                minv,maxv = maxv,minv
            
            maxv = max(maxv*nums[i],nums[i])
            minv = min(minv*nums[i],nums[i])

            ans = max(ans,maxv)
        return ans

这个代码通过在遍历数组时动态更新最小乘积和最大乘积，并在每一步更新全局最大乘积，从而找到最大的子数组乘积。