算法题：K 次取反后最大化的数组和（典型的贪心算法问题）

这道题没有看题解，直接提交，成绩超越99.5%，说明思路是优的。就是考虑的情况里面弯弯绕比较多，需要考虑全面一点。（本题完整题目附在了最后面）

具体思路如下：

1、首先排序，然后从最小的负数开始一一变为正数，如果遍历到正数了，而k的次数没用完，如果剩余的k是偶数次，则直接可以退出了；如果k是奇数次且nums内有0元素也可以直接退出程序；如果k是奇数次且nums里面没有0元素，则挑一个最小的正数，将其置为负数，其实也就是比较正在遍历到的数和前一个数的大小，小的那个就是nums数组里的最小正数。

2、还有一种情况就是，数组已经遍历完了，k没用完，这个也很简单，直接对数组的最后一个数，也就是数组里面最小非负数进行操作，如果其为0则直接退出，如果是k是偶数也可直接退出，如果k是奇数则将这个数置为负数。

3、最后对nums数组求和。

代码如下：

class Solution(object):def largestSumAfterKNegations(self, nums, k):nums.sort()for i in range(len(nums)):if k <= 0: breakif nums[i] < 0:nums[i] = 0 - nums[i]k -= 1elif nums[i] == 0:k = 0breakelse:# 这里的 k & 1 是判断k是否为奇数的快速判断方法if nums[i] > nums[i - 1] and k & 1:  nums[i - 1] = 0 - nums[i - 1]elif nums[i] <= nums[i - 1] and k & 1:nums[i] = 0 - nums[i]k = 0breakif k > 0 and k & 1:nums[-1] = 0 - nums[-1]return sum(nums)if __name__ == '__main__':sol = Solution()# print(sol.largestSumAfterKNegations([2, -3, -1, 5, -4], 2))print(sol.largestSumAfterKNegations([-4, -2, -3], 4))

完整题目：

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

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