本文主要是介绍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
这篇关于LeetCode 1749. 任意子数组和的绝对值的最大值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!