题目描述
给你一个整数数组 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
解法一：动态规划
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
func min(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num < res {
res = num
}
}
return res
}
func max(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func maxAbsoluteSum(nums []int) int {
n := len(nums)
dp := make([][2]int, n)
// dp[i][0]：以 nums[i] 结尾的子数组的最小和
// dp[i][1]：以 nums[i] 结尾的子数组的最大和
dp[0][0], dp[0][1] = nums[0], nums[0]
ans := abs(nums[0])
for i := 1; i < n; i++ {
if nums[i] < 0 {
dp[i][0] = min(dp[i-1][0]+nums[i], nums[i])
dp[i][1] = max(dp[i-1][1]+nums[i], nums[i])
} else {
dp[i][0] = min(dp[i-1][0]+nums[i], nums[i])
dp[i][1] = max(dp[i-1][1]+nums[i], nums[i])
}
ans = max(abs(dp[i][0]), abs(dp[i][1]), ans)
}
return ans
}
|
使用滚动数组优化上面代码：
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
func min(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num < res {
res = num
}
}
return res
}
func max(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func maxAbsoluteSum(nums []int) int {
n := len(nums)
var dp [2][2]int
// dp[i][0]：以 nums[i] 结尾的子数组的最小和
// dp[i][1]：以 nums[i] 结尾的子数组的最大和
dp[0][0], dp[0][1] = nums[0], nums[0]
ans := abs(nums[0])
for i := 1; i < n; i++ {
dp[1][0] = min(dp[0][0]+nums[i], nums[i])
dp[1][1] = max(dp[0][1]+nums[i], nums[i])
ans = max(abs(dp[1][0]), abs(dp[1][1]), ans)
dp[0] = dp[1]
}
return ans
}
|
解法二：前缀和
由于子数组和等于两个前缀和的差，那么取前缀和中的最大值与最小值，它俩的差就是答案。
如果最大值在最小值右边，那么算的是最大子数组和。
如果最大值在最小值左边，那么算的是最小子数组和的绝对值（相反数）。
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
28
29
30
31
32
33
34
35
36
37
|
func min(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num < res {
res = num
}
}
return res
}
func max(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func maxAbsoluteSum(nums []int) int {
n := len(nums)
prefixSum, minSum, maxSum := 0, 0, 0
for i := 0; i < n; i++ {
prefixSum += nums[i]
minSum = min(minSum, prefixSum)
maxSum = max(maxSum, prefixSum)
}
return abs(maxSum - minSum)
}
|
