Code Implementation

class Solution:
    def largestSumAfterKNegations(self, nums, k):
        nums.sort()
        i = 0
        # Flip as many negative numbers as possible
        while i < len(nums) and k > 0 and nums[i] < 0:
            nums[i] = -nums[i]
            i += 1
            k -= 1
        # If k is still odd, flip the smallest absolute value
        if k % 2 == 1:
            nums.sort()
            nums[0] = -nums[0]
        return sum(nums)
    

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

import java.util.*;
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0;
        while (i < nums.length && k > 0 && nums[i] < 0) {
            nums[i] = -nums[i];
            i++;
            k--;
        }
        Arrays.sort(nums);
        if (k % 2 == 1) {
            nums[0] = -nums[0];
        }
        int sum = 0;
        for (int n : nums) sum += n;
        return sum;
    }
}
    

var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a, b) => a - b);
    let i = 0;
    while (i < nums.length && k > 0 && nums[i] < 0) {
        nums[i] = -nums[i];
        i++;
        k--;
    }
    nums.sort((a, b) => a - b);
    if (k % 2 === 1) {
        nums[0] = -nums[0];
    }
    return nums.reduce((a, b) => a + b, 0);
};
    

Problem Description

You are given an integer array nums and an integer k. You can choose any element from nums and flip its sign (i.e., change nums[i] to -nums[i]). You can repeat this operation exactly k times, and you may choose the same element multiple times.

Your task is to maximize the sum of the array after performing k sign-flip operations. Return the largest possible sum.

• Each flip can be applied to any element (even the same element repeatedly).
• There is only one array given, and you must use exactly k flips.
• All elements are integers; they can be negative, zero, or positive.

Thought Process

At first glance, it might seem tempting to try all possible combinations of flips, but this would be very inefficient, especially for large arrays or large values of k.

The key insight is that flipping a negative number to positive increases the sum more than flipping a positive to negative (which decreases the sum). Therefore, we should prioritize flipping the most negative numbers first.

Once all negatives are flipped, if we still have flips left, flipping the smallest (in absolute value) element is optimal for any remaining flips, especially if k is odd.

By sorting the array and working from the smallest values upward, we can systematically maximize the sum in the minimum number of steps.

Solution Approach

• Step 1: Sort the Array
  • Sorting brings all negative numbers to the front, making it easy to access and flip them first.
• Step 2: Flip Negative Numbers
  • Iterate through the array, flipping negative numbers to positive, consuming one flip per number, until you run out of negative numbers or flips.
• Step 3: Handle Remaining Flips
  • If you still have flips left and the number is odd, flip the smallest (in absolute value) number. Flipping twice cancels out, so only an odd number of flips matters at this point.
• Step 4: Calculate the Sum
  • After all flips, sum the array for the answer.

This approach ensures that each flip contributes maximally to increasing the sum, and any leftover flips are used optimally.

Example Walkthrough

Suppose nums = [-4, -2, -3, 4, 3] and k = 4.

1. Sort the array: [-4, -3, -2, 3, 4]
2. Start flipping negatives:
   • Flip -4 → 4 (k=3): [4, -3, -2, 3, 4]
   • Flip -3 → 3 (k=2): [4, 3, -2, 3, 4]
   • Flip -2 → 2 (k=1): [4, 3, 2, 3, 4]
3. All negatives flipped, 1 flip left (k=1):
   • Find the smallest value (which is 2), flip it to -2: [4, 3, -2, 3, 4]
4. Sum the array: 4 + 3 + (-2) + 3 + 4 = 12

The maximum possible sum after 4 flips is 12.

Time and Space Complexity

• Brute-force approach:
  • Would try all possible combinations of flips, leading to exponential time complexity, which is infeasible for large arrays or large k.
• Optimized approach (as described):
  • Sorting the array: O(n log n)
  • Flipping negatives: O(n)
  • Final sum: O(n)
  • Total Time Complexity: O(n log n)
  • Space Complexity: O(1) if done in-place (except for the sort operation, which may use O(n) space depending on the language implementation).

Summary

The elegant solution to maximizing the sum after k negations is to flip all negative numbers first, then use any remaining flips on the smallest absolute value if needed. This is efficiently achieved by sorting the array and working through it linearly, yielding an O(n log n) algorithm that is both simple and powerful.

The key insight is that flipping negatives gives the biggest gain, and any leftover (odd) flips should be used on the smallest element to minimize loss. This strategy ensures the sum is as large as possible after exactly k operations.