Maximize Sum Of Array After K Negations

Problem

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Examples

Example 1

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Constraints

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

Solution

Method 1 – Greedy with Sorting

Intuition

To maximize the sum, flip the smallest (most negative) numbers first. If there are flips left after all negatives are positive, flip the smallest number (which will be positive) as needed. This greedy approach ensures the sum is maximized after exactly k negations.

Approach

1. Sort nums in ascending order.
2. Flip the sign of the smallest negative numbers up to k times.
3. If flips remain after all negatives are positive, flip the smallest number (could be positive) for the remaining odd flips.
4. Return the sum of the array.

Code

C++

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() && k > 0; ++i) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                --k;
            }
        }
        sort(nums.begin(), nums.end());
        if (k % 2 == 1) nums[0] = -nums[0];
        int ans = 0;
        for (int x : nums) ans += x;
        return ans;
    }
};

Go

func largestSumAfterKNegations(nums []int, k int) int {
    sort.Ints(nums)
    for i := 0; i < len(nums) && k > 0; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
            k--
        }
    }
    sort.Ints(nums)
    if k%2 == 1 {
        nums[0] = -nums[0]
    }
    ans := 0
    for _, x := range nums {
        ans += x
    }
    return ans
}

Java

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        Arrays.sort(nums);
        if (k % 2 == 1) nums[0] = -nums[0];
        int ans = 0;
        for (int x : nums) ans += x;
        return ans;
    }
}

Kotlin

class Solution {
    fun largestSumAfterKNegations(nums: IntArray, k: Int): Int {
        nums.sort()
        var k = k
        for (i in nums.indices) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i]
                k--
            }
        }
        nums.sort()
        if (k % 2 == 1) nums[0] = -nums[0]
        return nums.sum()
    }
}

Python

class Solution:
    def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
        nums.sort()
        if k % 2 == 1:
            nums[0] = -nums[0]
        return sum(nums)

Rust

impl Solution {
    pub fn largest_sum_after_k_negations(mut nums: Vec<i32>, mut k: i32) -> i32 {
        nums.sort();
        for i in 0..nums.len() {
            if nums[i] < 0 && k > 0 {
                nums[i] = -nums[i];
                k -= 1;
            }
        }
        nums.sort();
        if k % 2 == 1 {
            nums[0] = -nums[0];
        }
        nums.iter().sum()
    }
}

TypeScript

class Solution {
    largestSumAfterKNegations(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        for (let i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        nums.sort((a, b) => a - b);
        if (k % 2 === 1) nums[0] = -nums[0];
        return nums.reduce((a, b) => a + b, 0);
    }
}

Complexity

• ⏰ Time complexity: O(n log n) — for sorting the array.
• 🧺 Space complexity: O(1) — only a few variables are used.