问题
问题描述：给定一个整形数组 A，可以通过以下方式修改它：选择 i，将其反转 A[i] = -A[i]，重复 K 次，可以选择相同的i反转多次。要求返回反转之后的最大和。
栗子1：
输入：A = [4, 2, 3], K = 1
输出：5
A 变为 [4, -2, 3]
栗子2：
输入： A = [3, -1, 0, 2], K = 3
输出：6
A 变为 [3, 1, 0, 2]
栗子3：
输入：A = [2, -3, -1, 5, -4], K = 2
输出：13
A 变为 [2, 3, -1, 5, 4]
注意：
1 <= A.length <= 100001 <= K <= 10000-100 <= A[i] <= 100
想看英文的戳这里：原题地址
解题思路
首先有一个很重要的点是，如果对一个数进行偶数次的反转，它的值保持不变。
我的解法
为了让和最大，如果有负数，需要尽量让负数进行反转，减少正数的反转。所以会分为以下几种情况来考虑：
无负数，全为正数
-
如果
K为偶数，那么可以保持不变，最大值就是原先数组的和。因为可以对第一个数一直反转，反转2次就保持原值了。比如
A = [4,3,2]，K = 2，那么我们可以对4进行2次反转，结果不变。 -
如果
K为奇数，那么肯定有一个数需要变为负数。我们需要选择最小的数反转为负数，才能保证最大值。比如
A = [4,3,2]，K = 1，那么我们可以对最小数2进行1次反转，变成[4,3,-2]。
比如K = 5，偶数次的都可以忽略，因为对值无影响，所以我们最终计算的只是5 % 2 = 1次的反转，与上面分析一样。
有负数，有正数
在这种情况下，需要考虑K与负数个数negCount问题。
K <= negCount
如果 K <= negCount，那么很简单，排序后，只需要把前K个负数进行反转即可。
比如A = [2,-3,-1,5,-4]，K = 2，反转最小的 2 个负数即可，A 变成[2,3,-1,5,4]。
K > negCount
如果K > negCount，我们可以考虑将负数先全部反转，但是可能会涉及到反转正数的问题。
-
如果
k - negCount为偶数，那么剩余的次数落在正数头上。由于是2的倍数次反转，刚好可以抵消，正数保持不变。比如
A = [2,-3,-1,5,-4]，K = 5，由于负数有3个，那么刚好还剩2次反转，抵消，正数保持不变。 -
如果
k - negCount为奇数，则需要考虑是反转正数，还是将负数保持不变（即多余的1次落到负数头上）。这里需要考虑到
负数的最大值与正数的最小值绝对值大小问题。如果
负数的绝对值大，那么反转正数。比如A = [2,-6,-4,5,-8]，K = 4，那么A = [-2,6,4,5,8]。如果
正数的绝对值大，那么负数保持不变。比如A = [2,-3,-1,5,-4]，K = 4，那么A = [2,3,-1,5,4]。
代码如下：
// 53.66%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
// 存负数
var negArray = [Int]()
// 存正数
var posArray = [Int]()
var sum = 0
for a in A {
sum += a
if a <= 0 {
negArray.append(a)
} else {
posArray.append(a)
}
}
// 排序
negArray = negArray.sorted()
posArray = posArray.sorted()
// 需要考虑无负数的情况
if negArray.count == 0, posArray.count > 0 {
// 反转 2 次，抵消
if K % 2 == 0 {
return sum
} else {
return sum - 2 * posArray[0]
}
} else {
// 如果 K 大于负数的个数，就需要到处理正数，优先把正数反转 2 次，即保持不变
if K > negArray.count {
let leftCount = K - negArray.count
// count 表示需要反转负数的个数
var count = negArray.count
// 奇数，需要比较正数的最小值与负数的最大值的绝对值关系，如果是偶数，可以对负数全部操作。
if leftCount % 2 == 1 {
// 如果负数的绝对值小，则最后一个负数保持不变，相当于 2 次反转。
if posArray.count > 0 {
if -negArray.last! < posArray[0] {
count -= 1
} else {
// 负数反转的增益大于正数变负数，将正数转为负数
sum -= 2 * posArray[0]
}
} else {
count -= 1
}
}
// 反转负数
var i = 0
while i < count {
sum -= 2 * negArray[i]
i += 1
}
} else {
// 负数变正数
var i = 0
while i < K {
sum -= 2 * negArray[i]
i += 1
}
}
}
return sum
}
更简洁的解法
思路跟上面的差不多，但是没有分那么多种情况，是一个比较完整的思路。
先对整个数组进行排序，将前 K 个负数反转，最后需区分剩下的次数是奇数还是偶数。
如果是偶数，则无影响，如果是奇数，则需要减去最小值*2。
// 60.98%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
// 先排序
var sortedA = A.sorted()
// 对前面的负数进行反转
var i = 0
var j = 0
// 如果 K 大于负数的个数，最后需要判断是对哪个数进行反转
while j < K, i < sortedA.count, sortedA[i] < 0 {
sortedA[i] = -sortedA[i]
j += 1
i += 1
}
var sum = 0
var k = 0
// 记录最小的数
var minNum = Int.max
while k < sortedA.count {
sum += sortedA[k]
if sortedA[k] < minNum {
minNum = sortedA[k]
}
k += 1
}
// 如果剩余的 K - j 是奇数，则需要减去 2*最小的数
if (K - j) % 2 == 1 {
sum -= 2 * minNum
}
return sum
}
网友评论