class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
}
};
1749. 任意子数组和的绝对值的最大值
给你一个整数数组 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原站题解
python3 解法, 执行用时: 120 ms, 内存消耗: 24.7 MB, 提交时间: 2022-12-12 14:42:48
'''
思路：dp
'''
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
up, down, ans = 0, 0, 0
for v in nums:
up = up + v if up > 0 else v
down = down + v if down < 0 else v
ans = max(ans, abs(up), abs(down))
return ans
python3 解法, 执行用时: 120 ms, 内存消耗: 26.5 MB, 提交时间: 2022-12-12 14:41:36
'''
思路：前缀和
'''
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
n = len(nums)
presum = [0 for _ in range(n + 1)] #前缀和
for i in range(1, n+1):
presum[i] = presum[i-1] + nums[i-1]
presum.sort() #排序
return presum[n] - presum[0] #最大和最小的差距
python3 解法, 执行用时: 140 ms, 内存消耗: 25.4 MB, 提交时间: 2022-12-12 14:40:21
'''
思路：前缀和
计算前缀和数组，寻找最大前缀和、最小前缀和
如果最大前缀和、最小前缀和都是正数（或0），那么最大子数组和绝对值为最大前缀和
如果最大前缀和、最小前缀和都是负数（或0），那么最大子数组和绝对值为最小前缀和的绝对值
如果一个正数一个负数，那么最大子数组和绝对值为最大前缀和-最小前缀和
'''
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
maxpre, minpre = -inf, inf
for pre in accumulate(nums):
maxpre = max(pre, maxpre)
minpre = min(pre, minpre)
if minpre >= 0:
return maxpre
if maxpre <= 0:
return abs(minpre)
return maxpre - minpre
golang 解法, 执行用时: 48 ms, 内存消耗: 8.3 MB, 提交时间: 2023-08-08 07:42:49
func maxAbsoluteSum(nums []int) int {
kadane := func(arr []int) int {
maxEndingHere, maxSoFar := arr[0], arr[0]
for _, num := range arr[1:] {
maxEndingHere = max(num, maxEndingHere+num)
maxSoFar = max(maxSoFar, maxEndingHere)
}
return maxSoFar
}
maxSum := kadane(nums)
minSum := kadane(negate(nums))
return max(maxSum, minSum)
}
func negate(nums []int) []int {
result := make([]int, len(nums))
for i, num := range nums {
result[i] = -num
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 164 ms, 内存消耗: 28.4 MB, 提交时间: 2023-08-08 07:42:08
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
def kadane(arr):
max_ending_here = max_so_far = arr[0]
for num in arr[1:]:
max_ending_here = max(num, max_ending_here + num)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
max_sum = kadane(nums)
min_sum = kadane([-num for num in nums])
return max(max_sum, min_sum)