Maximize Sum Of Array After K Negations — Easy Problem & Solution

Problem statement

You are given an integer array nums and an integer k. Exactly k times, choose an index i and replace nums[i] with -nums[i]. The same index may be chosen more than once.

Return the largest possible sum of the array after the k negations.

Example 1

Input: nums = [-5,2,-1], k = 2
Output: 8
Explanation: Negate -5 and -1: [5,2,1].

Example 2

Input: nums = [1,3,-2], k = 2
Output: 4
Explanation: Negate -2, then one negation is left over; spend it on the smallest value 1: [-1,3,2].

Example 3

Input: nums = [0,-7], k = 5
Output: 7
Explanation: After flipping -7, the remaining four negations can all go to 0.

Constraints

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 10^4

How to solve Maximize Sum Of Array After K Negations

Each negation should hit the current minimum: that is the flip that raises the sum most (or lowers it least). Sorting once captures every such choice, and leftover negations only matter by their parity.

Approach

1. Sort nums ascending.
2. Walk from the left: while k > 0 and the value is negative, negate it and decrement k.
3. Sum the array. If k is still odd, subtract twice the smallest element (now the smallest absolute value).

Why it works

Negating x changes the sum by -2x, which is largest for the smallest x. While negatives remain, the most negative ones are the best targets and are disjoint, so flipping them in order is optimal. Once all values are non-negative, two flips on the same element cancel, so only k mod 2 matters, and the cheapest single flip is the one on the smallest value.

Complexity

• Time — O(n log n)
• Space — O(1) beyond the sort

Pitfalls

• When negatives run out with an odd k left, the smallest absolute value may be a number you just flipped — take the minimum after flipping.
• A zero absorbs any number of leftover negations for free.
• A min-heap that negates its top k times is also correct, at O(k log n).

Reference solution

Python

from typing import List

def largestSumAfterKNegations(nums: List[int], k: int) -> int:
    a = sorted(nums)
    for i in range(len(a)):
        if k > 0 and a[i] < 0:
            a[i] = -a[i]
            k -= 1
    total = sum(a)
    if k % 2 == 1:
        total -= 2 * min(a)
    return total

JavaScript

var largestSumAfterKNegations = function(nums, k) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    for (var i = 0; i < a.length && k > 0 && a[i] < 0; i++) {
        a[i] = -a[i];
        k--;
    }
    var total = 0, low = a[0];
    for (var j = 0; j < a.length; j++) {
        total += a[j];
        if (a[j] < low) low = a[j];
    }
    if (k % 2 === 1) total -= 2 * low;
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Available Captures for Rook Easy
• Delete Columns to Make Sorted Easy
• Nearest Smaller Element Easy
• Minimum Positive Sum Subarray Easy
• Find X-Sum of All K-Long Subarrays I Easy
• Valid Boomerang Easy