Easy

题目描述

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

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[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] 。

提示：

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

解题思路

这是一道贪心算法题目。我们的目标是通过 k 次取反操作使数组和最大化。

核心思路：

  1. 优先处理负数：由于取反可以将负数变为正数，我们应该优先对负数进行取反操作，这样能最大化地增加数组和。

  2. 按绝对值排序：为了贪心地选择每次取反的元素，我们按照绝对值从大到小排序。这样可以确保：

    • 优先取反绝对值大的负数（获得最大收益）
    • 如果负数处理完后还有剩余操作次数，选择绝对值最小的数进行反复取反

  3. 处理剩余操作：

    • 如果 k 次操作刚好用完所有负数，直接返回结果
    • 如果还有剩余操作次数，且次数为奇数，需要对当前绝对值最小的数取反
    • 如果剩余次数为偶数，相当于没有变化

算法步骤：

  1. 按绝对值从大到小排序
  2. 遍历数组，优先对负数取反，直到 k 用完或没有负数
  3. 如果 k 还有剩余且为奇数，对当前绝对值最小的数取反
  4. 计算最终数组和

这种方法时间复杂度为 O(n log n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b) {
            return abs(a) > abs(b);
        });
        
        for (int i = 0; i < nums.size() && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            nums[nums.size() - 1] = -nums[nums.size() - 1];
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
};

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=abs, reverse=True)
        
        for i in range(len(nums)):
            if k > 0 and nums[i] < 0:
                nums[i] = -nums[i]
                k -= 1
        
        if k % 2 == 1:
            nums[-1] = -nums[-1]
        
        return sum(nums)

public class Solution {
    public int LargestSumAfterKNegations(int[] nums, int k) {
        Array.Sort(nums, (a, b) => Math.Abs(b).CompareTo(Math.Abs(a)));
        
        for (int i = 0; i < nums.Length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            nums[nums.Length - 1] = -nums[nums.Length - 1];
        }
        
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        return sum;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length && k > 0; i++) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    
    if (k % 2 === 1) {
        nums.sort((a, b) => a - b);
        nums[0] = -nums[0];
    }
    
    return nums.reduce((sum, num) => sum + num, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(1)只使用常数级额外空间（不考虑排序的栈空间）

相关题目