問題
問題描述：給定一個整形數(shù)組 A，可以通過以下方式修改它：選擇 i，將其反轉(zhuǎn) A[i] = -A[i]，重復(fù) K 次，可以選擇相同的i反轉(zhuǎn)多次。要求返回反轉(zhuǎn)之后的最大和。
栗子1：
輸入：A = [4, 2, 3], K = 1
輸出：5
A 變?yōu)?[4, -2, 3]
栗子2：
輸入： A = [3, -1, 0, 2], K = 3
輸出：6
A 變?yōu)?[3, 1, 0, 2]
栗子3：
輸入：A = [2, -3, -1, 5, -4], K = 2
輸出：13
A 變?yōu)?[2, 3, -1, 5, 4]
注意：
1 <= A.length <= 100001 <= K <= 10000-100 <= A[i] <= 100
想看英文的戳這里：原題地址
解題思路
首先有一個很重要的點是，如果對一個數(shù)進(jìn)行偶數(shù)次的反轉(zhuǎn)，它的值保持不變。
我的解法
為了讓和最大，如果有負(fù)數(shù)，需要盡量讓負(fù)數(shù)進(jìn)行反轉(zhuǎn)，減少正數(shù)的反轉(zhuǎn)。所以會分為以下幾種情況來考慮：
無負(fù)數(shù)，全為正數(shù)
-
如果
K為偶數(shù)，那么可以保持不變，最大值就是原先數(shù)組的和。因為可以對第一個數(shù)一直反轉(zhuǎn)，反轉(zhuǎn)2次就保持原值了。比如
A = [4,3,2]，K = 2，那么我們可以對4進(jìn)行2次反轉(zhuǎn)，結(jié)果不變。 -
如果
K為奇數(shù)，那么肯定有一個數(shù)需要變?yōu)樨?fù)數(shù)。我們需要選擇最小的數(shù)反轉(zhuǎn)為負(fù)數(shù)，才能保證最大值。比如
A = [4,3,2]，K = 1，那么我們可以對最小數(shù)2進(jìn)行1次反轉(zhuǎn)，變成[4,3,-2]。
比如K = 5，偶數(shù)次的都可以忽略，因為對值無影響，所以我們最終計算的只是5 % 2 = 1次的反轉(zhuǎn)，與上面分析一樣。
有負(fù)數(shù)，有正數(shù)
在這種情況下，需要考慮K與負(fù)數(shù)個數(shù)negCount問題。
K <= negCount
如果 K <= negCount，那么很簡單，排序后，只需要把前K個負(fù)數(shù)進(jìn)行反轉(zhuǎn)即可。
比如A = [2,-3,-1,5,-4]，K = 2，反轉(zhuǎn)最小的 2 個負(fù)數(shù)即可，A 變成[2,3,-1,5,4]。
K > negCount
如果K > negCount，我們可以考慮將負(fù)數(shù)先全部反轉(zhuǎn)，但是可能會涉及到反轉(zhuǎn)正數(shù)的問題。
-
如果
k - negCount為偶數(shù)，那么剩余的次數(shù)落在正數(shù)頭上。由于是2的倍數(shù)次反轉(zhuǎn)，剛好可以抵消，正數(shù)保持不變。比如
A = [2,-3,-1,5,-4]，K = 5，由于負(fù)數(shù)有3個，那么剛好還剩2次反轉(zhuǎn)，抵消，正數(shù)保持不變。 -
如果
k - negCount為奇數(shù)，則需要考慮是反轉(zhuǎn)正數(shù)，還是將負(fù)數(shù)保持不變（即多余的1次落到負(fù)數(shù)頭上）。這里需要考慮到
負(fù)數(shù)的最大值與正數(shù)的最小值絕對值大小問題。如果
負(fù)數(shù)的絕對值大，那么反轉(zhuǎn)正數(shù)。比如A = [2,-6,-4,5,-8]，K = 4，那么A = [-2,6,4,5,8]。如果
正數(shù)的絕對值大，那么負(fù)數(shù)保持不變。比如A = [2,-3,-1,5,-4]，K = 4，那么A = [2,3,-1,5,4]。
代碼如下：
// 53.66%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
// 存負(fù)數(shù)
var negArray = [Int]()
// 存正數(shù)
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()
// 需要考慮無負(fù)數(shù)的情況
if negArray.count == 0, posArray.count > 0 {
// 反轉(zhuǎn) 2 次，抵消
if K % 2 == 0 {
return sum
} else {
return sum - 2 * posArray[0]
}
} else {
// 如果 K 大于負(fù)數(shù)的個數(shù)，就需要到處理正數(shù)，優(yōu)先把正數(shù)反轉(zhuǎn) 2 次，即保持不變
if K > negArray.count {
let leftCount = K - negArray.count
// count 表示需要反轉(zhuǎn)負(fù)數(shù)的個數(shù)
var count = negArray.count
// 奇數(shù)，需要比較正數(shù)的最小值與負(fù)數(shù)的最大值的絕對值關(guān)系，如果是偶數(shù)，可以對負(fù)數(shù)全部操作。
if leftCount % 2 == 1 {
// 如果負(fù)數(shù)的絕對值小，則最后一個負(fù)數(shù)保持不變，相當(dāng)于 2 次反轉(zhuǎn)。
if posArray.count > 0 {
if -negArray.last! < posArray[0] {
count -= 1
} else {
// 負(fù)數(shù)反轉(zhuǎn)的增益大于正數(shù)變負(fù)數(shù)，將正數(shù)轉(zhuǎn)為負(fù)數(shù)
sum -= 2 * posArray[0]
}
} else {
count -= 1
}
}
// 反轉(zhuǎn)負(fù)數(shù)
var i = 0
while i < count {
sum -= 2 * negArray[i]
i += 1
}
} else {
// 負(fù)數(shù)變正數(shù)
var i = 0
while i < K {
sum -= 2 * negArray[i]
i += 1
}
}
}
return sum
}
更簡潔的解法
思路跟上面的差不多，但是沒有分那么多種情況，是一個比較完整的思路。
先對整個數(shù)組進(jìn)行排序，將前 K 個負(fù)數(shù)反轉(zhuǎn)，最后需區(qū)分剩下的次數(shù)是奇數(shù)還是偶數(shù)。
如果是偶數(shù)，則無影響，如果是奇數(shù)，則需要減去最小值*2。
// 60.98%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
// 先排序
var sortedA = A.sorted()
// 對前面的負(fù)數(shù)進(jìn)行反轉(zhuǎn)
var i = 0
var j = 0
// 如果 K 大于負(fù)數(shù)的個數(shù)，最后需要判斷是對哪個數(shù)進(jìn)行反轉(zhuǎn)
while j < K, i < sortedA.count, sortedA[i] < 0 {
sortedA[i] = -sortedA[i]
j += 1
i += 1
}
var sum = 0
var k = 0
// 記錄最小的數(shù)
var minNum = Int.max
while k < sortedA.count {
sum += sortedA[k]
if sortedA[k] < minNum {
minNum = sortedA[k]
}
k += 1
}
// 如果剩余的 K - j 是奇數(shù)，則需要減去 2*最小的數(shù)
if (K - j) % 2 == 1 {
sum -= 2 * minNum
}
return sum
}
