LeetCode 1005: Maximize Sum Of Array After K Negations (Greedy by Absolute Value Priority)

2026-04-09 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 1005GreedySorting

Today we solve LeetCode 1005 - Maximize Sum Of Array After K Negations.

Source: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

LeetCode 1005 greedy negation diagram showing abs-desc sorting, flip negatives first, then optional smallest abs flip

English

Problem Summary

Given integer array nums and integer k, you may choose an index and negate that value exactly k times (same index can be chosen repeatedly). Return the maximum possible array sum.

Key Insight

Negating a negative number increases sum the most when its absolute value is large. So process numbers by descending absolute value: flip every negative while operations remain. If operations are still odd after that, flip the element with the smallest absolute value once.

Algorithm

- Sort nums by absolute value descending.
- Traverse from left to right: if nums[i] < 0 and k > 0, negate it and decrement k.
- After traversal, if k is odd, negate the last element (smallest absolute value).
- Return the sum of array.

Complexity Analysis

Time: O(n log n) due to sorting.
Space: O(log n) to O(n) depending on sort implementation.

Common Pitfalls

- Sorting by numeric value instead of absolute value.
- Forgetting the leftover odd-k adjustment.
- Flipping a random element at the end instead of the smallest absolute value element.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) arr[i] = nums[i];
        Arrays.sort(arr, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a)));

        for (int i = 0; i < arr.length && k > 0; i++) {
            if (arr[i] < 0) {
                arr[i] = -arr[i];
                k--;
            }
        }

        if ((k & 1) == 1) arr[arr.length - 1] = -arr[arr.length - 1];

        int sum = 0;
        for (int v : arr) sum += v;
        return sum;
    }
}

func largestSumAfterKNegations(nums []int, k int) int {
    sort.Slice(nums, func(i, j int) bool {
        ai, aj := nums[i], nums[j]
        if ai < 0 { ai = -ai }
        if aj < 0 { aj = -aj }
        return ai > aj
    })

    for i := 0; i < len(nums) && k > 0; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
            k--
        }
    }

    if k%2 == 1 {
        nums[len(nums)-1] = -nums[len(nums)-1]
    }

    sum := 0
    for _, v := range nums {
        sum += v
    }
    return sum
}

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b) {
            return abs(a) > abs(b);
        });

        for (int i = 0; i < (int)nums.size() && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }

        if (k % 2 == 1) nums.back() = -nums.back();

        int sum = 0;
        for (int v : nums) sum += v;
        return sum;
    }
};

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: -abs(x))

        for i in range(len(nums)):
            if k > 0 and nums[i] < 0:
                nums[i] = -nums[i]
                k -= 1

        if k % 2 == 1:
            nums[-1] = -nums[-1]

        return sum(nums)

var largestSumAfterKNegations = function(nums, k) {
  nums.sort((a, b) => Math.abs(b) - Math.abs(a));

  for (let i = 0; i < nums.length && k > 0; i++) {
    if (nums[i] < 0) {
      nums[i] = -nums[i];
      k--;
    }
  }

  if (k % 2 === 1) {
    nums[nums.length - 1] = -nums[nums.length - 1];
  }

  return nums.reduce((acc, v) => acc + v, 0);
};

中文

题目概述

给定整数数组 nums 和整数 k，你必须进行恰好 k 次取反操作（同一位置可以多次取反），目标是让数组元素和最大，返回最大和。

核心思路

优先翻转“绝对值大且为负数”的元素，收益最大。因此先按绝对值从大到小排序：能翻的负数先翻。最后若剩余 k 为奇数，再翻转绝对值最小的元素一次。

算法步骤

- 将数组按绝对值降序排序。
- 从左到右遍历：若当前值为负且 k > 0，执行取反并 k--。
- 遍历后如果 k 仍为奇数，取反最后一个元素（绝对值最小）。
- 返回数组总和。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：取决于语言排序实现，约为 O(log n) 到 O(n)。

常见陷阱

- 按数值排序而不是按绝对值排序。
- 忘记处理剩余奇数次操作。
- 最后翻错元素，应该翻绝对值最小的那个。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) arr[i] = nums[i];
        Arrays.sort(arr, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a)));

        for (int i = 0; i < arr.length && k > 0; i++) {
            if (arr[i] < 0) {
                arr[i] = -arr[i];
                k--;
            }
        }

        if ((k & 1) == 1) arr[arr.length - 1] = -arr[arr.length - 1];

        int sum = 0;
        for (int v : arr) sum += v;
        return sum;
    }
}

func largestSumAfterKNegations(nums []int, k int) int {
    sort.Slice(nums, func(i, j int) bool {
        ai, aj := nums[i], nums[j]
        if ai < 0 { ai = -ai }
        if aj < 0 { aj = -aj }
        return ai > aj
    })

    for i := 0; i < len(nums) && k > 0; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
            k--
        }
    }

    if k%2 == 1 {
        nums[len(nums)-1] = -nums[len(nums)-1]
    }

    sum := 0
    for _, v := range nums {
        sum += v
    }
    return sum
}

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b) {
            return abs(a) > abs(b);
        });

        for (int i = 0; i < (int)nums.size() && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }

        if (k % 2 == 1) nums.back() = -nums.back();

        int sum = 0;
        for (int v : nums) sum += v;
        return sum;
    }
};

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: -abs(x))

        for i in range(len(nums)):
            if k > 0 and nums[i] < 0:
                nums[i] = -nums[i]
                k -= 1

        if k % 2 == 1:
            nums[-1] = -nums[-1]

        return sum(nums)

var largestSumAfterKNegations = function(nums, k) {
  nums.sort((a, b) => Math.abs(b) - Math.abs(a));

  for (let i = 0; i < nums.length && k > 0; i++) {
    if (nums[i] < 0) {
      nums[i] = -nums[i];
      k--;
    }
  }

  if (k % 2 === 1) {
    nums[nums.length - 1] = -nums[nums.length - 1];
  }

  return nums.reduce((acc, v) => acc + v, 0);
};