Maximize sum of array after k negations

Array Greedy Sorting

53.6% acceptance

Feb 25, 2026

1705

125

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn largest_sum_after_k_negations(nums: Vec<i32>, k: i32) -> i32 {
    let mut a = nums;
    a.sort_by_key(|&x| x.abs());
    let mut k = k;
    for x in a.iter_mut().rev() {
      if *x < 0 && k > 0 { *x = -*x; k -= 1; }
    }
    if k % 2 == 1 { *a.iter_mut().min_by_key(|&&mut x| x).unwrap() *= -1; }
    a.iter().sum()
  }
}