Maximize Sum Of Array After K Negations

Problem Description

So, you’ve got an array of integers, and you’re allowed to flip the sign of up to k negative numbers. The goal here is to maximize the sum of the array after performing these flips.

Imagine you’re at a buffet, and you can only eat a certain number of dishes (let’s say k dishes). You want to make sure you pick the most delicious ones (or in this case, the least negative ones) to maximize your overall satisfaction (or sum).

Code Solution


class Solution {
 public:
  int largestSumAfterKNegations(vector& 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;
  }
};

Approach Explanation

The approach here is quite straightforward. First, we sort the array to bring the negative numbers to the front. Then, we iterate through the array and flip the signs of the negative numbers until we either run out of negative numbers or exhaust our k flips. Finally, we calculate the total sum of the array. If we still have flips left (and they’re odd), we flip the smallest number (which could be negative or positive) to maximize the sum.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re at a party with a bunch of friends, and they’re all complaining about how bad the snacks are. You have the power to make them say nice things about the snacks (flipping their negativity). If you can only change a few of their minds (up to k), you want to make sure you pick the most negative ones to flip. By the end of the party, you want everyone to be raving about how great the snacks are (maximizing the sum of their opinions)!