LeetCode 152. Maximum Product Subarray 题解

LeetCode 152. Maximum Product Subarray 题解题目描述给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。示例 1输入nums [2,3,-2,4] 输出6 解释子数组 [2,3] 有最大乘积 6。示例 2输入nums [-2,0,-1] 输出0 解释结果不能为 2, 因为 [-2,-1] 不是子数组。解题思路方法动态规划思路由于乘法的特殊性当遇到负数时最大值可能会变成最小值最小值可能会变成最大值因此我们需要同时跟踪当前的最大值max_product和最小值min_product状态转移方程max_product max(nums[i], max_product * nums[i], min_product * nums[i])min_product min(nums[i], max_product * nums[i], min_product * nums[i])最终结果为所有max_product中的最大值复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法动态规划class Solution: def maxProduct(self, nums: List[int]) - int: n len(nums) if n 0: return 0 max_product nums[0] min_product nums[0] result nums[0] for i in range(1, n): # 临时保存当前的 max_product因为它会被更新 temp_max max_product max_product max(nums[i], temp_max * nums[i], min_product * nums[i]) min_product min(nums[i], temp_max * nums[i], min_product * nums[i]) result max(result, max_product) return result测试用例测试用例 1输入nums [2,3,-2,4]输出6测试用例 2输入nums [-2,0,-1]输出0测试用例 3输入nums [-2,3,-4]输出24测试用例 4输入nums [0,2]输出2总结本题是动态规划的经典问题主要考察对状态定义和状态转移方程的理解。由于乘法的特殊性我们需要同时跟踪当前的最大值和最小值。动态规划的核心思想是通过遍历数组同时维护当前的最大值和最小值根据当前元素的正负性来更新这两个值从而找到整个数组的最大乘积子数组。这种方法不仅适用于最大乘积子数组问题还可以应用于许多其他需要同时跟踪最大值和最小值的问题。掌握动态规划的思想对于解决这类问题非常重要。