题目

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

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 10^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

    解题方法

    贪心

    若有负数，首先翻转最小的负数；若无负数且k%2==1则翻转最小的非负数。随后求和即可。
    时间复杂度O(nlogn)，空间复杂度O(1)
    C++代码：
    1. class Solution {
    2. public:
    3.   int largestSumAfterKNegations(vector<int>& nums, int k) {
    4.       sort(nums.begin(), nums.end());
    5.       for(int i=0; i<nums.size() && k>0; i++) {
    6.           if(nums[i]<0) {
    7.               nums[i] *= -1;
    8.               k--;
    9.           }
    10.           else break;
    11.       }
    12.       sort(nums.begin(), nums.end());
    13.       if(k%2) nums[0] *= -1;
    14.       int sum = 0;
    15.       for(int num : nums) sum += num;
    16.       return sum;
    17.   }
    18. };