前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

• 六六力扣刷题贪心算法之基础和最大子序和
• 六六力扣刷题贪心算法之买卖股票的最佳时机
• 六六力扣刷题贪心算法之买卖股票的最佳时机2
• 六六力扣刷题贪心算法之买卖股票的最佳时机含手续费
• 六六力扣刷题贪心算法之跳跃游戏
• 六六力扣刷题贪心算法之分发饼干

题目

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

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

示例 1：

• 输入：A = [4,2,3], K = 1
• 输出：5
• 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：

• 输入：A = [3,-1,0,2], K = 3
• 输出：6
• 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

• 输入：A = [2,-3,-1,5,-4], K = 2
• 输出：13
• 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

• 1 <= A.length <= 10000
• 1 <= K <= 10000
• -100 <= A[i] <= 100

思路

本题思路其实比较好想了，如何可以让数组和最大呢？

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大

实现步骤： 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

• 先排序
• 遍历排序后的数组，有负值且还有转换次数就转正
• 再排序有三种情况

• 转换次数已经用完 此时直接返回即可
• 转换次数没用完 还剩偶数次，此时没有负数了，直接返回即可
• 转换次数没用完 还剩偶数次，此时没有负数了，返回sum-2*最小数

代码

package com.six.finger.leetcode.five;
import java.util.Arrays;
import java.util.stream.IntStream;
public class twentynine {
    public static void main(String[] args) {
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        //首排序
        Arrays.sort(nums);
        //定义一个res
        int res = 0;
        // 遍历排序后的数组，有负值且还有转换次数就转正
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] < 0 && k > 0) {
                nums[i] = -1 * nums[i];
                k--;
            }
            res += nums[i];
        }
        // 再排序有三种情况 1. 转换次数已经用完 此时直接返回即可
        //                 2.转换次数没用完 还剩偶数次，此时没有负数了，直接返回即可
        //                 3.转换次数没用完 还剩偶数次，此时没有负数了，返回sum-2*最小数,为啥是减去2次，大家注意下，因为我们之前多加了一次
        Arrays.sort(nums);
        return res - (k % 2 == 0? 0 : 2 * nums[0]);
    }
}

结束

其实这题怎么说呢？好像感觉不是那么难，但是得细心分析下，好了，我是小六六，三天打鱼，两天晒网！