[leetcode]动态规划-最大子数组和

最大子数组和系列题目的核心算法是Kadane算法：定义状态f[i]表示以a[i]结尾的最大子数组和，不和i左边拼起来就是f[i] = a[i]，和i左边拼起来就是f[i] = f[i-1] + a[i]，取最大值就得到了状态转移方程f[i] = max(f[i-1], 0) + a[i]，答案为max(f)。

子数组非空

53. 最大子数组和 [Medium] 1186. 删除一次得到子数组最大和 [Medium] 918. 环形子数组的最大和 [Medium]

# 53. 最大子数组和 class Solution: def maxSubArray(self, nums: List[int]) -> int: n=len(nums) # 子数组非空 f=[nums[0]]+[0]*(n-1) # 子数组可以为空： # f=[0]*n for i in range(1,n): f[i]=max(f[i-1],0)+nums[i] return max(f)

最大子数组和系列主要有两类，子数组可以为空和子数组非空。如果子数组非空，那么f数组初始化为f=[nums[0]]+[0]*(n-1)，如果优化空间，不定义数组，那么ans必须初始化为-inf：

class Solution: def maxSubArray(self, nums: List[int]) -> int: # 子数组非空 ans, f = -inf, 0 # 子数组可以为空 # ans = f = 0 for x in nums: f = max(f, 0) + x ans = max(ans, f) return ans # 1186. 删除一次得到子数组最大和 class Solution: def maximumSum(self, arr: List[int]) -> int: f=[[-inf,-inf]]+[[0,0] for _ in arr] for i,x in enumerate(arr): f[i+1][0]=max(f[i][0],0)+x f[i+1][1]=max(f[i][1]+x,f[i][0]) return max(max(r) for r in f)

这题涉及到枚举每个元素时删或不删，有点类似状态机DP。同样地，子数组非空，所以f初始状态为-inf。

# 918. 环形子数组的最大和 class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: fmax,ansMax,fmin,ansMin=0,-inf,0,0 for x in nums: fmax=max(fmax,0)+x ansMax=max(ansMax,fmax) fmin=min(fmin,0)+x ansMin=min(ansMin,fmin) # ansMax<0表示nums中元素全负，返回负值最小的 return max(ansMax,sum(nums)-ansMin) if ansMax>0 else ansMax

这题要同时求求最大子数组和和最小子数组和。

子数组可以为空

2606. 找到最大开销的子字符串 [Medium] 1749. 任意子数组和的绝对值的最大值 [Medium] 1191. K 次串联后最大子数组之和 [Medium] 2321. 拼接数组的最大分数 [Hard]

# 2606. 找到最大开销的子字符串 class Solution: def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int: value_dict = dict(zip(chars, vals)) # 子数组可以为空 f=[0]*(len(s)+1) for i,c in enumerate(s): f[i+1] = max(f[i],0) + value_dict.get(c, ord(c)-ord('a')+1) # 优化空间 # ans = f = 0 # for c in enumerate(s): # f = max(f,0) + value_dict.get(c, ord(c)-ord('a')+1) # ans = max(ans, f) # return ans return max(f)

这道题就是子数组可以为空，所以f数组初始化为 f = [0]*(len(s)+1)

# 1749. 任意子数组和的绝对值的最大值 class Solution: def maxAbsoluteSum(self, nums: List[int]) -> int: ans = fmax = fmin = 0 for x in nums: fmax = max(fmax, 0) + x fmin = min(fmin, 0) + x ans = max(ans, fmax, -fmin) return ans

这题是求绝对值的最大值，所以要算最大子数组和和最小子数组和，最后取两者的最大值。

# 1191. K 次串联后最大子数组之和 MOD=10**9+7 class Solution: # kadane算法, 用于求解最大子数组和 def kadane(self,nums:List[int])->int: ans=f=0 for x in nums: f=max(f,0)+x ans=max(ans,f) return ans def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: if k==1: return self.kadane(arr) twoMax=self.kadane(arr*2) if sum(arr)<0: return twoMax%MOD else: return (twoMax+sum(arr)*(k-2))%MOD

子数组可以为空，ans初始化为0。

# 2321. 拼接数组的最大分数 class Solution: def kadane(self,nums1,nums2): ans=f=0 for x,y in zip(nums1,nums2): f=max(f,0)+y-x ans=max(ans,f) return sum(nums1)+ans def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int: return max(self.kadane(nums1,nums2),self.kadane(nums2,nums1)) 拓展 - 乘积最大子数组

152. 乘积最大子数组 [Medium] 2708. 一个小组的最大实力值 [Medium]

# 152. 乘积最大子数组 class Solution: def maxProduct(self, nums: List[int]) -> int: ans=-inf fmax=fmin=1 for x in nums: #fmin=min(fmax*x,fmin*x,x) #fmax和fmin必须写在同一表达式同时更新，分开先后更新的话，后更新的就会使用新的值，导致错误 fmax,fmin=max(fmax*x,fmin*x,x),min(fmax*x,fmin*x,x) ans=max(ans,fmax) return ans

乘积也是需要求最大乘积子数组和最小乘积子数组，因为负负得正，最小乘积子数组也可能变成最大乘积子数组。

# 2708. 一个小组的最大实力值 class Solution: def maxStrength(self, nums: List[int]) -> int: # 子数组非空 mx=mn=nums[0] for x in nums[1:]: mx,mn=max(mx,mx*x,mn*x,x),min(mn,mx*x,mn*x,x) return mx

以上整理自leetcode灵神题单：动态规划之 1.3 最大子数组和