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

题目描述#

给你一个整数数组 nums。定义一个子数组的和的绝对值为：

abs(nums[l] + nums[l+1] + ... + nums[r])

其中 abs(x) 的含义如下：

如果 x 是负整数，那么 abs(x) = -x
如果 x 是非负整数，那么 abs(x) = x

请你找出 nums 中和的绝对值最大的任意子数组（子数组也可以为空），并返回这个最大值。

知识边界#

这道题的核心在于把“子数组和”转化为“前缀和之差”，并进一步利用最大前缀和与最小前缀和之间的差值来求解。

1. 前缀和#

前缀和是解决连续子数组问题的常见工具。

设：

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

那么子数组 nums[l...r] 的和可以表示为：

prefix[r+1] - prefix[l]

也就是说，任意一个子数组和，本质上都是两个前缀和的差。

因此，本题要求：

max(|prefix[j] - prefix[i]|)

其中 i < j。

要让这个绝对值最大，本质上就是让两个前缀和之间的差距尽可能大，因此只需要维护：

前缀和中的最大值 preMax
前缀和中的最小值 preMin

答案就是：

preMax - preMin

因为较大值减较小值一定非负，它本身就是最大绝对差。

2. 为什么空子数组也能自然处理#

题目说明子数组可以为空。空子数组的和为 0。

在前缀和模型里，初始前缀和就是 0，因此只要一开始令：

prefix := 0
preMax := 0
preMin := 0

就已经把空子数组的情况包含进去了，不需要额外处理。

3. Go 中的变量维护方式#

在 Go 中，可以在一次遍历中同时维护：

当前前缀和 prefix
历史最大前缀和 preMax
历史最小前缀和 preMin

示例：

prefix := 0
preMax, preMin := 0, 0

for _, x := range nums {
	prefix += x
	if prefix > preMax {
		preMax = prefix
	}
	if prefix < preMin {
		preMin = prefix
	}
}

这种写法时间复杂度是 O(n)，空间复杂度是 O(1)。

4. Go 中的辅助函数写法#

Go 没有内置的整数 abs 函数，因此通常需要自己实现：

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

同时，很多题目里也会自己写 max 函数：

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

不过本题其实最终直接返回 preMax - preMin 即可，不一定需要 abs。

5. 常见错误点#

错误一：只考虑最大子数组和#

有些同学会想到经典的 Kadane 算法，只求“最大子数组和”。但本题要求的是“绝对值最大”，所以还要考虑“最小子数组和（最负）”，因为一个很小的负数取绝对值后也可能很大。

例如：

nums = [-10, 1, 2]

最大子数组和是 3，但答案其实是 10。

错误二：前缀和初始值不设为 0#

如果没有把 0 作为初始前缀和，就会漏掉从下标 0 开始的子数组，也无法正确覆盖空子数组。

错误三：把答案写成两个绝对值比较#

例如写成：

max(abs(preMax-preMin), abs(preMin-preMax))

虽然结果没错，但这是重复计算。因为：

abs(preMax - preMin) == abs(preMin - preMax)

而且由于 preMax >= preMin，直接写：

preMax - preMin

最简洁。

思路#

这道题可以从两个角度理解，最终都能得到线性时间解法。

思路一：前缀和 + 最大最小前缀值#

设当前遍历到某个位置时，前缀和为 prefix。

任意子数组和都可以表示成两个前缀和之差：

subSum = prefix[j] - prefix[i]

那么子数组和绝对值的最大值，就是让两个前缀和之间的距离最大。

因此只需要在遍历过程中记录：

历史最小前缀和 preMin
历史最大前缀和 preMax

最后答案就是：

preMax - preMin

正确性分析#

因为任意子数组和都等于两个前缀和的差，所以任意子数组和的绝对值都不会超过“最大前缀和与最小前缀和的差”。

另一方面，如果我们取到：

一个最小前缀和 preMin
一个最大前缀和 preMax

那么它们之间的差值一定对应某一段连续区间的和，因此这个差值是可以被某个子数组实际取得的。

所以最大绝对值一定就是：

preMax - preMin

时间复杂度#

只遍历一次数组，所以时间复杂度为 O(n)

空间复杂度#

只使用常数个变量，所以空间复杂度为 O(1)

思路二：分别求最大子数组和与最小子数组和#

还可以从经典动态规划角度理解。

对于任意子数组和的绝对值最大值，其实等于下面两者中的较大值：

最大子数组和
最小子数组和的绝对值

即：

max(maxSubSum, -minSubSum)

其中：

maxSubSum 可以用 Kadane 算法求
minSubSum 也可以用类似方法求

这种方法同样是 O(n) 时间、O(1) 空间。

正确性分析#

任意子数组和要么是一个较大的正数，要么是一个绝对值很大的负数。

所以只要分别求出：

所有子数组中的最大和
所有子数组中的最小和

再取绝对值较大的那个即可。

时间复杂度#

一次遍历即可完成，时间复杂度为 O(n)

空间复杂度#

只需若干状态变量，空间复杂度为 O(1)

相比之下，前缀和最大最小值的方法更直接，也更容易解释本题本质。

代码#

package main

func maxAbsoluteSum(nums []int) int {
	preMax := 0
	preMin := 0
	prefix := 0

	for _, x := range nums {
		prefix += x
		if prefix < preMin {
			preMin = prefix
		}
		if prefix > preMax {
			preMax = prefix
		}
	}

	return preMax - preMin
}