2025.12.1
乘积最大子数组
由于可能出现两个负数相乘，考虑同时记录最大子数组与最小子数组，两个数组都由上述两个转移而来。
class Solution:def maxProduct(self, nums: list[int]) -> int:n=len(nums)dpmax=nums.copy()dpmin=nums.copy()for i in range(1,n):dpmax[i]=max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],dpmax[i])dpmin[i]=min(dpmin[i-1]*nums[i],dpmax[i-1]*nums[i],dpmin[i])return(max(dpmax))
print(Solution().maxProduct([2,3,-2,4]))