给你一个整数数组 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
方法一：动态规划 + 分情况讨论
思路
一个变量绝对值的最大值，可能是这个变量的最大值的绝对值，也可能是这个变量的最小值的绝对值。题目要求任意子数组和的绝对值的最大值，可以分别求出子数组和的最大值 positiveMax 和子数组和的最小值 negativeMin，因为子数组可以为空，所以 positiveMax} \geq 0 ，negativeMin} \leq 0 。最后返回 \max(\textit{positiveMax}, -\textit{negativeMin}) 即为任意子数组和的绝对值的最大值。
而求子数组和的最大值，可以参照「53. 最大子数组和」 的解法，运用动态规划求解。而求子数组和的最小值，也是类似的思路，遍历时记录全局最小值 negativeMin 和当前子数组负数和并更新，遍历完即可得到子数组和的最小值。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
positiveMax, negativeMin = 0, 0
positiveSum, negativeSum = 0, 0
for n in nums:
positiveSum += n
positiveMax = max(positiveMax, positiveSum)
positiveSum = max(0, positiveSum)
negativeSum += n
negativeMin = min(negativeMin, negativeSum)
negativeSum = min(0, negativeSum)
return max(positiveMax, -negativeMin)
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int positiveMax = 0, negativeMin = 0;
int positiveSum = 0, negativeSum = 0;
for (int num : nums) {
positiveSum += num;
positiveMax = max(positiveMax, positiveSum);
positiveSum = max(0, positiveSum);
negativeSum += num;
negativeMin = min(negativeMin, negativeSum);
negativeSum = min(0, negativeSum);
}
return max(positiveMax, -negativeMin);
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
| int maxAbsoluteSum(int* nums, int numsSize) {
int positiveMax = 0, negativeMin = 0;
int positiveSum = 0, negativeSum = 0;
for (int i = 0; i < numsSize; i++) {
positiveSum += nums[i];
positiveMax = fmax(positiveMax, positiveSum);
positiveSum = fmax(0, positiveSum);
negativeSum += nums[i];
negativeMin = fmin(negativeMin, negativeSum);
negativeSum = fmin(0, negativeSum);
}
return fmax(positiveMax, -negativeMin);
}
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxAbsoluteSum(int[] nums) {
int positiveMax = 0, negativeMin = 0;
int positiveSum = 0, negativeSum = 0;
for (int num : nums) {
positiveSum += num;
positiveMax = Math.max(positiveMax, positiveSum);
positiveSum = Math.max(0, positiveSum);
negativeSum += num;
negativeMin = Math.min(negativeMin, negativeSum);
negativeSum = Math.min(0, negativeSum);
}
return Math.max(positiveMax, -negativeMin);
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public int MaxAbsoluteSum(int[] nums) {
int positiveMax = 0, negativeMin = 0;
int positiveSum = 0, negativeSum = 0;
foreach (int num in nums) {
positiveSum += num;
positiveMax = Math.Max(positiveMax, positiveSum);
positiveSum = Math.Max(0, positiveSum);
negativeSum += num;
negativeMin = Math.Min(negativeMin, negativeSum);
negativeSum = Math.Min(0, negativeSum);
}
return Math.Max(positiveMax, -negativeMin);
}
}
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func maxAbsoluteSum(nums []int) int {
positiveMax, negativeMin := 0, 0
positiveSum, negativeSum := 0, 0
for _, num := range nums {
positiveSum += num
positiveMax = max(positiveMax, positiveSum)
positiveSum = max(0, positiveSum)
negativeSum += num
negativeMin = min(negativeMin, negativeSum)
negativeSum = min(0, negativeSum)
}
return max(positiveMax, -negativeMin)
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
| var maxAbsoluteSum = function(nums) {
let positiveMax = 0, negativeMin = 0;
let positiveSum = 0, negativeSum = 0;
for (let num of nums) {
positiveSum += num
positiveMax = Math.max(positiveMax, positiveSum)
positiveSum = Math.max(0, positiveSum)
negativeSum += num
negativeMin = Math.min(negativeMin, negativeSum)
negativeSum = Math.min(0, negativeSum)
}
return Math.max(positiveMax, -negativeMin)
};
|
复杂度分析
时间复杂度：O(n)。只需要遍历数组一遍。
空间复杂度：O(1)。仅使用常数空间。
