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

题目链接

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和

示例:

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

思路

解法一：

解题关键：取反一个负数总和变大，取反正数总和变小

  1. 先按绝对值从大到小排序
  2. 若num小于0，则将num取正值，k减一
  3. 若k为奇数，则将绝对值最小的数符号取反，累加元素即为结果
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums = sorted(nums, key=abs, reverse=True)
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
        if k % 2 == 1:
            nums[-1] = -nums[-1]
        res = 0
        for i in range(len(nums)):
            res += nums[i]
        return res