Maximize Sum After K Negations

Maximize array sum by flipping signs of k elements using greedy heap approach

Language Selection

Choose your preferred programming language

Showing: Python

Maximize Sum After K Negations

Problem Statement

Given an integer array nums and an integer k, modify the array in the following way:

Choose exactly k indices (possibly the same index more than once) and flip the sign of the integers at those indices.

Return the largest possible sum of the array after modifying it in this way.

Input/Output Specifications

Input:
- nums: Array of integers
- k: Integer representing number of negations allowed
Output: Integer representing maximum possible sum

Constraints

1 <= nums.length <= 10^4
-100 <= nums[i] <= 100
1 <= k <= 10^4

Examples

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 (nums[1] = 2) and flip it: [4,-2,3]. Sum = 4 + (-2) + 3 = 5.

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices 1, 1, 2 (flip -1 twice and 0 once): [3,1,0,2]. Sum = 3 + 1 + 0 + 2 = 6.

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices 1, 4 (flip -3 and -4): [2,3,-1,5,4]. Sum = 2 + 3 + (-1) + 5 + 4 = 13.

Solution Approaches

Approach 1: Min-Heap (Greedy)

Algorithm Explanation:

Use min-heap to always flip the smallest element
For k operations:
- Extract minimum element
- Flip its sign and put back
After k operations, sum all elements

Implementation:

Python:

import heapq

def largest_sum_after_k_negations(nums, k):
    """
    Maximize sum using min-heap for greedy negations
    Time: O(n log n + k log n)
    Space: O(n)
    """
    # Create min-heap
    heap = nums[:]
    heapq.heapify(heap)
    
    # Perform k negations
    for _ in range(k):
        min_val = heapq.heappop(heap)
        heapq.heappush(heap, -min_val)
    
    return sum(heap)

# Optimized approach - negate negatives first
def largest_sum_after_k_negations_optimized(nums, k):
    """
    Optimized approach focusing on negative numbers first
    Time: O(n log n)
    Space: O(1) if sorting in place
    """
    nums.sort()
    
    # First, negate all negative numbers (up to k operations)
    for i in range(len(nums)):
        if nums[i] < 0 and k > 0:
            nums[i] = -nums[i]
            k -= 1
    
    # If k is still positive and odd, negate the smallest positive number
    if k % 2 == 1:
        nums.sort()
        nums[0] = -nums[0]
    
    return sum(nums)

Java:

import java.util.*;

class Solution {
    /**
     * Maximize sum using min-heap
     * Time: O(n log n + k log n)
     * Space: O(n)
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        // Convert to list and create min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
        }
        
        // Perform k negations
        for (int i = 0; i < k; i++) {
            int min = minHeap.poll();
            minHeap.offer(-min);
        }
        
        // Calculate sum
        int sum = 0;
        while (!minHeap.isEmpty()) {
            sum += minHeap.poll();
        }
        
        return sum;
    }
    
    /**
     * Optimized approach without heap
     * Time: O(n log n)
     * Space: O(1)
     */
    public int largestSumAfterKNegationsOptimized(int[] nums, int k) {
        Arrays.sort(nums);
        
        // Negate negative numbers first
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        // If k is odd, negate the smallest element
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        
        return Arrays.stream(nums).sum();
    }
}

Go:

import (
    "container/heap"
    "sort"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// largestSumAfterKNegations - Maximize sum using min-heap
// Time: O(n log n + k log n), Space: O(n)
func largestSumAfterKNegations(nums []int, k int) int {
    minHeap := &MinHeap{}
    
    // Build heap
    for _, num := range nums {
        *minHeap = append(*minHeap, num)
    }
    heap.Init(minHeap)
    
    // Perform k negations
    for i := 0; i < k; i++ {
        min := heap.Pop(minHeap).(int)
        heap.Push(minHeap, -min)
    }
    
    // Calculate sum
    sum := 0
    for minHeap.Len() > 0 {
        sum += heap.Pop(minHeap).(int)
    }
    
    return sum
}

// Optimized version without heap
func largestSumAfterKNegationsOptimized(nums []int, k int) int {
    sort.Ints(nums)
    
    // Negate negatives first
    for i := 0; i < len(nums) && k > 0; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
            k--
        }
    }
    
    // If k is odd, negate smallest element
    if k%2 == 1 {
        sort.Ints(nums)
        nums[0] = -nums[0]
    }
    
    sum := 0
    for _, num := range nums {
        sum += num
    }
    
    return sum
}

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let minChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] < this.heap[minChildIdx]) {
                minChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] <= this.heap[minChildIdx]) break;
            [this.heap[idx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[idx]];
            idx = minChildIdx;
        }
    }
}

/**
 * Maximize sum using min-heap
 * Time: O(n log n + k log n)
 * Space: O(n)
 */
function largestSumAfterKNegations(nums, k) {
    const minHeap = new MinHeap();
    
    // Add all numbers to heap
    for (const num of nums) {
        minHeap.push(num);
    }
    
    // Perform k negations
    for (let i = 0; i < k; i++) {
        const min = minHeap.pop();
        minHeap.push(-min);
    }
    
    // Calculate sum
    let sum = 0;
    while (minHeap.size() > 0) {
        sum += minHeap.pop();
    }
    
    return sum;
}

/**
 * Optimized approach without heap
 * Time: O(n log n)
 * Space: O(1)
 */
function largestSumAfterKNegationsOptimized(nums, k) {
    nums.sort((a, b) => a - b);
    
    // Negate negative numbers first
    for (let i = 0; i < nums.length && k > 0; i++) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    
    // If k is odd, negate the smallest element
    if (k % 2 === 1) {
        nums.sort((a, b) => a - b);
        nums[0] = -nums[0];
    }
    
    return nums.reduce((sum, num) => sum + num, 0);
}

Key Insights

Greedy Strategy: Always flip the smallest element to maximize sum increase
Negative Priority: Flip negative numbers first (biggest impact)
Odd/Even K: If remaining k is odd, flip smallest positive number
Heap Efficiency: Min-heap automatically maintains smallest element at top

Edge Cases

All Positive: Only flip if k is odd (flip smallest)
All Negative: Flip largest negatives first
Contains Zero: Zero is optimal target for odd remaining flips
k > Array Length: May need to flip same elements multiple times

Test Cases

def test_largest_sum_after_k_negations():
    # Example 1
    assert largest_sum_after_k_negations([4,2,3], 1) == 5
    
    # Example 2
    assert largest_sum_after_k_negations([3,-1,0,2], 3) == 6
    
    # Example 3
    assert largest_sum_after_k_negations([2,-3,-1,5,-4], 2) == 13
    
    # All positive with odd k
    assert largest_sum_after_k_negations([1,2,3], 1) == 4  # [1,2,-3] = 0, wrong. Should be [-1,2,3] = 4
    
    # All negative
    assert largest_sum_after_k_negations([-1,-2,-3], 2) == 4  # [1,2,-3] = 0, wrong. Should be [1,2,-3] = 0
    
    # Test optimized version
    assert largest_sum_after_k_negations_optimized([4,2,3], 1) == 5
    assert largest_sum_after_k_negations_optimized([2,-3,-1,5,-4], 2) == 13
    
    print("All tests passed!")

test_largest_sum_after_k_negations()

Interview Tips

Greedy Insight: Explain why flipping smallest element is optimal
Negative Numbers: Prioritize flipping negative numbers first
Remaining Operations: Handle case when k operations remain after flipping negatives
Heap vs Sorting: Compare approaches and their trade-offs
Edge Cases: All positive, all negative, contains zero

Follow-up Questions

Minimize Sum: What if we want to minimize the sum instead?
Limited Flips Per Element: Each element can be flipped at most once
Weighted Elements: Elements have different weights
Multiple Arrays: Apply strategy across multiple arrays
Online Algorithm: Handle elements arriving dynamically

Common Mistakes

Wrong Strategy: Not prioritizing negative numbers for flipping
Odd/Even Logic: Not handling remaining k operations correctly
Heap Management: Incorrect heap operations
Edge Cases: Not handling all positive or all negative arrays
Optimization: Not recognizing that sorting once can be more efficient than heap

Concept Explanations

Greedy Optimality: Flipping the smallest element always provides the maximum increase in sum. For negative numbers, flipping makes them positive (large gain). For positive numbers, we want to flip the smallest to minimize loss.

Two-Phase Strategy: First phase flips negative numbers (guaranteed positive impact). Second phase handles remaining operations on the smallest positive number if k is odd.

When to Apply: This pattern works for optimization problems where each operation has a local optimal choice that contributes to the global optimum. The key is recognizing when greedy choices lead to optimal solutions.