贪心
解题思路
局部最优：让绝对值大的负数变为正数，当前数值达到最大；
整体最优：整个数组和达到最大；
贪心思路：
- 先将 nums [2, -3, -1, 5, -4] 进行 绝对值降序排序 后，会变成 [5, -4, -3, 2, -1] 则可以从 最小负数 开始反转，这样求和会更大；
- 迭代 nums 数组并开始对 负数 开始反转
k--；- 如果负数全部反转完成后 k 还是大于 0 ，则需要对最小的数字不断反转剩下的次数即可；前面的 绝对值降序排序 会将最小值放到最后，直接对最小值反转剩下的次数；
- 返回数组的求和结果；
复杂度
-
时间复杂度:
O(nlogn)，其中 n 为数组长度，排序花费了O(nlogn)； -
空间复杂度:
O(1)；
代码实现
var largestSumAfterKNegations = function (nums, k) {
// 1. 绝对值降序排序 => 最小的负数在最前面
nums.sort((a, b) => Math.abs(b) - Math.abs(a));
for (let i = 0; i < nums.length; i++) {
// 2. 对负数进行取反
if (nums[i] < 0 && k > 0) {
nums[i] = - nums[i];
k--;
}
}
// 3. 若 k 还大于 0，则寻找最小的数进行不断取反
while (k--) nums[nums.length - 1] = - nums[nums.length - 1];
return nums.reduce((a, b) => a + b, 0);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 45. 跳跃游戏Ⅱ
上一篇
评论
