Skip to content

1005. Maximize Sum Of Array After K Negations 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int largestSumAfterKNegations(vector<int>& nums, int k) {
    ranges::sort(nums);

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

    return accumulate(nums.begin(), nums.end(), 0) -
           (k % 2) * ranges::min(nums) * 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int largestSumAfterKNegations(int[] nums, int k) {
    Arrays.sort(nums);

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

    return Arrays.stream(nums).sum() - (k % 2) * Arrays.stream(nums).min().getAsInt() * 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
    nums.sort()

    for i, num in enumerate(nums):
      if num > 0 or k == 0:
        break
      nums[i] = -num
      k -= 1

    return sum(nums) - (k % 2) * min(nums) * 2