8. K 次取反后最大化的数组和（1005）

一、题目内容 简单

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

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

示例1：

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

示例2：

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

示例3：

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

二、解题思路

先将数组按绝对值，从大到小排序。
然后遍历数组，遇到小于 0 的数，换成 -num[i]，同时 k--
遍历结束后，如果 k > 0，把数组最后一位，也就是最小的一位，依次反转。
最后算出数组和。

三、具体代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function (nums, k) {
  nums.sort((a, b) => Math.abs(b) - Math.abs(a));
  for (let i in nums) {
    if (nums[i] < 0 && k > 0) {
      nums[i] *= -1;
      k--;
    }
  }
  if (k % 2) nums[nums.length - 1] *= -1;
  return nums.reduce((sum, cur) => cur + sum, 0);
};
/**
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */

四、其他解法