給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，按以下方法修改該數(shù)組：
選擇某個(gè)下標(biāo) i 并將 nums[i] 替換為 -nums[i] 。
重復(fù)這個(gè)過程恰好 k 次?？梢远啻芜x擇同一個(gè)下標(biāo) i 。
以這種方式修改數(shù)組后，返回?cái)?shù)組 可能的最大和 。
其中
1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104

例子

輸入：nums = [4,2,3], k = 1
輸出：5
解釋：選擇下標(biāo) 1 ，nums 變?yōu)?[4,-2,3] 。

輸入：nums = [3,-1,0,2], k = 3
輸出：6
解釋：選擇下標(biāo) (1, 2, 2) ，nums 變?yōu)?[3,1,0,2] 。

輸入：nums = [2,-3,-1,5,-4], k = 2
輸出：13
解釋：選擇下標(biāo) (1, 4) ，nums 變?yōu)?[2,3,-1,5,4] 。

解題思路

題意稍微解釋下, 給定個(gè)數(shù)組nums, 次數(shù)k, 將數(shù)組內(nèi)任意元素, 做k次取反操作, 一個(gè)元素可取多次
找到k次完成之后數(shù)組各元素相加的最大和

• 現(xiàn)將數(shù)組正序排列
• 先順序把負(fù)數(shù)變正數(shù)
  • 如果k無剩余, 直接返回相加和
  • 如果k有剩余, 判斷剩余k的奇偶性
    • 偶數(shù): 直接求和
    • 奇數(shù): 找到最小做一次反轉(zhuǎn), 再求和

這里把負(fù)數(shù)變正, 應(yīng)該很好理解, 稍微解釋下剩余k為何奇偶判斷

以 nums = [2,-3,-1,5,-4], k=10 和 k=11 舉例:

先正序數(shù)組, 負(fù)數(shù)變正數(shù) 數(shù)組為 [1, 2, 3, 4, 5], 需要消耗3次, 此時(shí)全正數(shù)求和最大為15
全正數(shù)之后, 只針對(duì)最小數(shù)做剩余次數(shù)取反就行, 因?yàn)樽銎渌疾粫?huì)為最大

• [-1, 2, 3, 4, 5] 和為 13
• [1, 2, 3, 4, -5] 和為 5

那么
k=11

剩余8次, 偶數(shù), 可對(duì)首值做偶數(shù)次取反結(jié)構(gòu)不變
可做到正序數(shù)組不變, [1, 2, 3, 4, 5], 滿足找到最大

k=10

剩余7次, 奇數(shù), 那么我們把最小值取反即可 [-1, 2, 3, 4, 5], 滿足找到最大

未翻譯版

    func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
        
        var temp = nums.sorted(), kd = k

        for i in 0..<temp.count {
            if temp[i] > 0 { break }
            temp[i] = -temp[i]
            kd -= 1
            if kd == 0 { break }
        }
        
        if kd > 0 && kd % 2 == 1 {
            temp = temp.sorted()
            temp[0] = -temp[0]
        }
        
        return temp.reduce(0,+)
    }

翻譯版

    func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
        
        // 定位temp為正序數(shù)組, 次數(shù)kd為 k
        var temp = nums.sorted(), kd = k

        // 遍歷temp
        for i in 0..<temp.count {
             
            // 如果temp[i] 大于 0, 彈出循環(huán)
            if temp[i] > 0 { break }
          
            // 如果temp[i] 小于 0 取反
            temp[i] = -temp[i]

            // 次數(shù)-1
            kd -= 1

            // 如果沒有次數(shù)了 彈出循環(huán)
            if kd == 0 { break }
        }
        
        // 如果次數(shù)剩余, 并且剩余次數(shù)為奇數(shù), 做最小值取反
        if kd > 0 && kd % 2 == 1 {
            temp = temp.sorted()
            temp[0] = -temp[0]
        }
        
        // 數(shù)組元素求和返回結(jié)果
        return temp.reduce(0,+)
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址