Maximize array sum after K negations

Problem Statement

Given an array of integers and a number k, modify the array by negating at most k elements such that the sum of the array is maximized.

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ k ≤ 10^4
• -10^9 ≤ arr[i] ≤ 10^9

Example:

• Input: arr = [4, 2, 3], k = 1
• Output: 5
• Explanation: We can negate nothing or negate the smallest positive. Wait, all are positive. If k=1, we can flip 2 to -2, but that reduces sum. So best is original: 4+2+3=9. Actually, we must use k? No, "at most k" negations. So answer is 9.

Example 2:

• Input: arr = [9, 8, 8, 5], k = 3
• Output: 20
• Explanation: All positive, no benefit to negate. Sum = 30. But wait, if we must use k... The problem typically says "exactly k" or "at most k". Let's assume we can choose.

Example 3:

• Input: arr = [-2, 0, 5, -1], k = 4
• Output: 8
• Explanation: Negate -2 and -1 to get [2, 0, 5, 1]. Sum = 8.

Approach 1: Brute Force (Simulate K Negations)

Intuition

For each of k negations, find the smallest element and negate it. Repeat k times.

Algorithm

1. For each negation (1 to k):
   • Find minimum element
   • Negate it
2. Return sum of array

public class Solution {
    public long maxSumBrute(int[] arr, int k) {
        int[] nums = arr.clone();
        
        for (int i = 0; i < k; i++) {
            int minIdx = 0;
            for (int j = 1; j < nums.length; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            
            nums[minIdx] = -nums[minIdx];
        }
        
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        return sum;
    }
}

Complexity Analysis

• Time Complexity: O(n * k) - k iterations, each finding minimum in O(n)
• Space Complexity: O(n) - Copy of array

Approach 2: Sort and Greedy - Optimal

Intuition

Sort the array. Negate negative numbers starting from the most negative. If k is still left after all negatives are positive, toggle the smallest element repeatedly.

Key Insight:

• Negating a negative number increases the sum
• If all numbers are positive, negating the smallest (repeatedly if needed) minimizes loss

Algorithm

1. Sort the array
2. Negate negative numbers from left (most negative first)
3. If k operations remain and k is odd, negate the smallest absolute value element
4. Return sum

import java.util.*;

public class MaxSumAfterNegations {
    
    public long maxSum(int[] arr, int k) {
        int n = arr.length;
        
        // Sort the array
        Arrays.sort(arr);
        
        int i = 0;
        
        // Negate negative numbers
        while (i < n && k > 0 && arr[i] < 0) {
            arr[i] = -arr[i];
            i++;
            k--;
        }
        
        // If k is odd, negate smallest element
        if (k % 2 == 1) {
            Arrays.sort(arr);
            arr[0] = -arr[0];
        }
        
        // Calculate sum
        long sum = 0;
        for (int num : arr) {
            sum += num;
        }
        
        return sum;
    }
    
    // Using PriorityQueue
    public long maxSumHeap(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.offer(num);
        }
        
        // Perform k negations
        for (int i = 0; i < k; i++) {
            int minVal = minHeap.poll();
            minHeap.offer(-minVal);
        }
        
        long sum = 0;
        while (!minHeap.isEmpty()) {
            sum += minHeap.poll();
        }
        
        return sum;
    }
    
    public static void main(String[] args) {
        MaxSumAfterNegations msn = new MaxSumAfterNegations();
        
        System.out.println(msn.maxSum(new int[]{4, 2, 3}, 1));  // 9
        System.out.println(msn.maxSum(new int[]{-2, 0, 5, -1}, 4));  // 8
        System.out.println(msn.maxSum(new int[]{3, -1, 0, 2}, 3));  // 6
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(1) if sorting in place, O(n) otherwise

Using Min-Heap Approach

Time Complexity: O(k log n) - k heap operations

Key Takeaways

1. Greedy Choice: Always negate the smallest element
2. Negative First: Negating negatives converts them to positives (increases sum)
3. Odd K Remaining: If k is odd after all negatives are handled, one negation remains
4. Zero Handling: Zero is ideal for remaining odd k (no change to sum)
5. Even K Remainder: Even remaining k cancels out (negate-negate = original)
6. Min-Heap Alternative: Efficient for large k with heap operations
7. Sort Once: Sort to process negatives efficiently