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

🟢   🔖  贪心 数组 排序  🔗 力扣 LeetCode

题目

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: nums = [4,2,3], k = 1

Output: 5

Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3

Output: 6

Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2

Output: 13

Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Constraints:

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

题目大意

给你一个整数数组 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

解题思路

1. 将数组从小到大排序，这样可以优先对负数进行取反，从而快速增加数组总和。

2. 使用一个循环，尝试进行最多 k 次取反操作：

   • 如果当前元素是负数，则将其取反；
   • 如果当前元素是非负数，并且还未完成所有 k 次操作，则找到当前绝对值最小的元素并取反。

3. 每次取反操作后，更新记录当前数组中绝对值最小的元素索引 min。

4. 遍历数组并计算总和，返回最终结果。

复杂度分析

• 时间复杂度：O(n log n)
  • 初始排序：O(n log n)。
  • 遍历数组并执行取反：O(k)。
  • 数组求和：O(n)。
  • 总时间复杂度：O(n log n)。
• 空间复杂度：O(1)，使用了常量级额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function (nums, k) {
	// 对数组从小到大排序
	nums.sort((a, b) => a - b);
	let min = 0; // 初始化最小值索引

	// 进行 k 次操作
	for (let i = 0; i < k; i++) {
		// 更新最小值索引
		if (nums[i] < nums[min]) min = i;

		// 如果当前数是负数，则取反
		if (nums[i] < 0) {
			nums[i] = -nums[i];
		} else {
			// 如果遇到非负数，优先取反绝对值最小的数
			nums[min] = -nums[min];
		}
	}

	// 返回数组的总和
	return nums.reduce((acc, cur) => acc + cur, 0);
};

相关题目

题号	标题	题解	标签	难度	力扣
2099	找到和最大的长度为 K 的子序列	[✓]	数组 哈希表 排序 1+	🟢	🀄️ 🔗