LeetCode 1749. 任意子数组和的绝对值的最大值

题目

思路

 这道题我在刚开始做时是想的动态规划的做法。考虑到已有和最大子数组的动态规划解法，本题要求绝对值最大的子数组，因此再维护一个以当前元素结尾的子数组和最小的数组，绝对值最大的数一定在和最大和和最小中产生。后来借鉴了其他大神的解法，这道题可以先求出前缀和数组，然后用其中的最大值和最小值相减即可（因为题目是求绝对值最大，因此不用考虑前缀和中减数和被减数的位置关系）

class Solution:def maxAbsoluteSum(self, nums: List[int]) -> int:n=len(nums)dp1=[-float('inf') for i in range(n)]dp2=[float('inf') for i in range(n)]ans=abs(nums[0])dp1[0]=nums[0]dp2[0]=nums[0]for i in range(1,n):if dp1[i-1]>=0:dp1[i]=dp1[i-1]+nums[i]else:dp1[i]=nums[i]if dp2[i-1]>=0:dp2[i]=nums[i]else:dp2[i]=dp2[i-1]+nums[i]ans=max(max(abs(dp1[i]),abs(dp2[i])),ans)#print(dp1,dp2)return ans