题目描述

解题思路

贪心思路：
第一次贪心：（如果负数大于k）
局部最优：就是每次变换变换绝对值最大的数，整体最优：整个数组和达到最大。
第二次贪心：（如果负数小于k，负数变完之后，还剩正数）
局部最优：变换最小的正数，全局最优：整个 数组和 达到最大。
那么本题的解题步骤为：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K—
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完

• 第四步：求和

  写法一

  public int largestSumAfterKNegations(int[] A, int K) {
    if (A.length == 1) return K % 2 == 1 ? -A[0] : A[0];
    Arrays.sort(A);
    int index = 0;
    for (int i = 0; i < K; i++) {
        // 如果为负数，那就变为相反数
        if (i < A.length - 1 && A[index] < 0) {
            A[index] = -A[index];
            // 如果变化之后大于等于后边数的绝对值，那么index++
            // [1,3,2,6,7,9]
            // 3
            // 注意需要判断，否则全为正数就会不满足贪心
            if (A[index] >= Math.abs(A[index + 1])) index++;
            // 下一步不执行了
            continue;
        }
        // 最终负数消耗完了，但是还有正数，所以一直利用最小的一个正数，把k消耗完
        A[index] = -A[index];
    }
    // 统计总和
    int sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
    }
    return sum;
  }

  写法二

  使用stream直接对绝对值排序

  public int largestSumAfterKNegations(int[] nums, int k) {
        int result = 0;
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        for (int i = 0; i < nums.length; i++) {
            // 从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && k > 0) {
                nums[i] = Math.abs(nums[i]);
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.length - 1] = 0 - nums[nums.length - 1];    // 如果K还大于0，那么反复转变数值最小的元素，将K用完
        // 求和
        for (int i : nums) {
            result += i;
        }
        return result;
    }