【算法题】1749. 任意子数组和的绝对值的最大值(LeetCode)
【算法题】1749. 任意子数组和的绝对值的最大值(LeetCode)
1.题目
下方是力扣官方题目的地址
给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
abs(x) 定义如下：
- 如果
x是负整数，那么abs(x) = -x。 - 如果
x是非负整数，那么abs(x) = x。
示例 1：
输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
示例 2：
输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
2.题解
思路
它要求我们求绝对值的最大值，我们可以直接求出两个最值：最大值和最小值，然后将它们的绝对值做作比较，取最大。
那么如何求一个数组的子数组和的最大值或最小值呢？
我们可以用动态规划的方法
我们以求最大值为例，最小值就将max改成min就行
我们定义dp[i]为以i为结尾的子数组的最大值
这就有了两种情况：
第一种：只有nums[i]这一个数构成的子数组
第二种：继承dp[i-1]的子数组并加上nums[i]
哪个情况大选哪一种
所以代码就是：
nums = [1,-3,2,3,-4]
dp=[0]*len(nums)
dp[0]=nums[0]
for i in range(1,len(nums)):
dp[i]=max(nums[i],dp[i-1]+nums[i])
print(dp)
# 输出： [1, -2, 2, 5, 1]
然后将求最小值的结合起来，将二者的绝对值作比较就最大就行了
Python代码
class Solution(object):
def maxAbsoluteSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp1=[0]*len(nums)
dp1[0]=nums[0]
dp2=[0]*len(nums)
dp2[0]=nums[0]
for i in range(1,len(nums)):
dp1[i]=min(nums[i],dp1[i-1]+nums[i])
dp2[i]=max(nums[i],dp2[i-1]+nums[i])
return max(abs(max(dp2)),abs(min(dp1)))
3.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。
原文地址：https://blog.csdn.net/Janium/article/details/142992475
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！