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

题目

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

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
• 重复这个过程恰好 k 次。可以多次选择同一个下标 i。

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

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

方法：贪心算法

贪心算法的思路就是通过局部最优推出整体最优，应用到该题中就是，尽可能修改负数，将其值变为正数。若将负数全都变为正数后 k 仍大于零，那么应修改此时的最小值（即最小的正数或零），最终得到最大和

• 将 nums 内元素按照绝对值的大小进行从大到小的排序
• 循环遍历数组。若 k > 0 且元素值小于零，那么将该元素变为正数，并且 k--
• 若在遍历后 k 仍旧大于零，那么此时应该修改数组中的最小值
• 返回更新后的数组元素和

class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        nums = sorted(nums, key = abs, reverse = True)
        for i in range(len(nums)):
            if k > 0 and nums[i] < 0:
                nums[i] *= -1
                k -= 1
        if k > 0:
            nums[-1] *= (-1)**k 
        return sum(nums)

相关知识

• sorted(iterable, key=None, reverse=False)： sorted()
  iterable： 可迭代对象
  key： 排序规则
  reverse： 默认 False，即升序

参考

代码相关：https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
sorted：http://c.biancheng.net/view/2239.html