IOS 算法(基础篇) ----- K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
其中
1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104

例子

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

解题思路

题意稍微解释下, 给定个数组nums, 次数k, 将数组内任意元素, 做k次取反操作, 一个元素可取多次
找到k次完成之后数组各元素相加的最大和

• 现将数组正序排列
• 先顺序把负数变正数
  • 如果k无剩余, 直接返回相加和
  • 如果k有剩余, 判断剩余k的奇偶性
    • 偶数: 直接求和
    • 奇数: 找到最小做一次反转, 再求和

这里把负数变正, 应该很好理解, 稍微解释下剩余k为何奇偶判断

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

先正序数组, 负数变正数 数组为 [1, 2, 3, 4, 5], 需要消耗3次, 此时全正数求和最大为15
全正数之后, 只针对最小数做剩余次数取反就行, 因为做其他都不会为最大

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

那么
k=11

剩余8次, 偶数, 可对首值做偶数次取反结构不变
可做到正序数组不变, [1, 2, 3, 4, 5], 满足找到最大

k=10

剩余7次, 奇数, 那么我们把最小值取反即可 [-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为正序数组, 次数kd为 k
        var temp = nums.sorted(), kd = k

        // 遍历temp
        for i in 0..<temp.count {
             
            // 如果temp[i] 大于 0, 弹出循环
            if temp[i] > 0 { break }
          
            // 如果temp[i] 小于 0 取反
            temp[i] = -temp[i]

            // 次数-1
            kd -= 1

            // 如果没有次数了 弹出循环
            if kd == 0 { break }
        }
        
        // 如果次数剩余, 并且剩余次数为奇数, 做最小值取反
        if kd > 0 && kd % 2 == 1 {
            temp = temp.sorted()
            temp[0] = -temp[0]
        }
        
        // 数组元素求和返回结果
        return temp.reduce(0,+)
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址