leetcode 1005. K 次取反后最大化的数组和

题目描述

给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。

示例 1:
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。

示例 2:
输入:A = [3,-1,0,2], K = 3
输出:6
解释:选择索引 (1, 2, 2) ,然后 A 变为 [3,1,0,2]。

示例 3:
输入:A = [2,-3,-1,5,-4], K = 2
输出:13
解释:选择索引 (1, 4) ,然后 A 变为 [2,3,-1,5,4]。

提示:

  1. 1 <= A.length <= 10000
  2. 1 <= K <= 10000
  3. -100 <= A[i] <= 100

题解

比较反转的次数K和多少个负数nums,主要分两种情况,K < nums时,就反转K个最小的负数,k >= nums时,则看看K-nums是奇数还是偶数,偶数就反转两次不变,奇数就再减去最小值(数组A变为正整数中的最小值)

示例代码(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
28
29
func largestSumAfterKNegations(A []int, K int) int {
res, nums, min := 0, 0, 101
sort.Ints(A)
for _, v := range A {
if v < 0 {
nums++
}
if min > abs(v) {
min = abs(v)
}
res += abs(v)
}
if K < nums {
for i := K; i < nums; i++ {
res += 2*A[i]
}

} else if (K-nums) % 2 == 1 {
res -= 2*min
}
return res
}

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