# Maximize Sum Of Array After K Negations
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximize-sum-of-array-after-k-negations)
Canonical: https://scaleengineer.com/dsa/problems/maximize-sum-of-array-after-k-negations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Druva](https://scaleengineer.com/companies/druva)
---
## Problem
Given an integer array `nums` and an integer `k`, modify the array in the following way:

* choose an index `i` and replace `nums[i]` with `-nums[i]`.

You should apply this process exactly `k` times. You may choose the same index `i` multiple times.

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

**Example 1:**

**Input:** nums = [4,2,3], k = 1
**Output:** 5
**Explanation:** Choose index 1 and nums becomes [4,-2,3].

**Example 2:**

**Input:** nums = [3,-1,0,2], k = 3
**Output:** 6
**Explanation:** Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

**Example 3:**

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

**Constraints:**

* `1 <= nums.length <= 104`
* `-100 <= nums[i] <= 100`
* `1 <= k <= 104`

# Approaches
## Brute Force Simulation
This approach directly simulates the given process. It iterates `k` times, and in each iteration, it finds the smallest element in the array and negates it. This is the most straightforward way to implement the logic but is not the most efficient.
**Time:** O(k * N). To find the minimum element, we must scan the entire array of size N. This operation is repeated `k` times, leading to a total time complexity of O(k * N). · **Space:** O(1). The array is modified in-place, so no extra space proportional to the input size is used.
**Pros:** Simple to understand and implement.; Follows the problem description literally.; Uses constant extra space.
**Cons:** Highly inefficient for large values of `k` and `N`, as it repeatedly scans the entire array.; Likely to result in a "Time Limit Exceeded" error on platforms with strict time limits for the given constraints.
### Explanation
The core idea is to repeatedly perform the operation that seems best at the current moment: negating the smallest number to get the largest possible immediate increase in sum. We loop exactly `k` times. In each iteration, we perform a linear scan of the entire array to find the minimum value and its index. Once found, we flip its sign. After `k` iterations, the array is in its final state, and we compute the sum of all its elements.

```java
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            int minIndex = 0;
            for (int j = 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            nums[minIndex] = -nums[minIndex];
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}
```
### Algorithm
*   Initialize a loop to run `k` times.
*   Inside the loop, find the index `minIndex` of the smallest element in the array `nums` by iterating through it.
*   Negate the element at this index: `nums[minIndex] = -nums[minIndex]`.
*   After the loop completes, iterate through the modified `nums` array one last time to calculate the total sum.
*   Return the calculated sum.

## Using a Min-Heap (Priority Queue)
To optimize the process of finding the minimum element in each step, we can use a min-heap. A min-heap is a data structure that allows us to retrieve the minimum element in logarithmic time, which is a significant improvement over the linear scan of the brute-force approach.
**Time:** O(N + k log N). Building the heap from N elements takes O(N) time. Each of the `k` negations involves a poll and an add operation, both taking O(log N) time. Summing the final elements also takes time, contributing to the overall complexity. · **Space:** O(N). We need to store all N elements in the priority queue.
**Pros:** Significantly faster than the brute-force approach for large N.; The logic is a direct simulation of the greedy strategy but uses an optimized data structure for finding the minimum.
**Cons:** Requires extra space to store the heap, proportional to the size of the input array.; Can be slightly less efficient than the sorting approach if `k` is very large, as it performs `k` heap operations regardless of the array's state.
### Explanation
This approach replaces the O(N) search for the minimum with an O(log N) operation from a min-heap. First, we build a min-heap from all the numbers in the input array, which takes O(N) time. Then, we perform the negation operation `k` times. In each step, we extract the minimum element, negate it, and insert it back. Extracting the minimum (`poll()`) and inserting an element (`add()`) both take O(log N) time. After `k` such operations, the heap contains the elements of the modified array. We then sum up all elements in the heap to get the final answer.

```java
import java.util.PriorityQueue;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.add(num);
        }

        for (int i = 0; i < k; i++) {
            int smallest = pq.poll();
            pq.add(-smallest);
        }

        int sum = 0;
        while (!pq.isEmpty()) {
            sum += pq.poll();
        }
        return sum;
    }
}
```
### Algorithm
*   Create a min-heap (in Java, a `PriorityQueue`) and insert all elements from `nums` into it.
*   Loop `k` times:
    *   Extract the minimum element from the heap using `poll()`.
    *   Negate this element.
    *   Insert the negated element back into the heap using `add()`.
*   After the loop, the heap contains the final elements. Sum them up by repeatedly polling from the heap until it's empty.
*   Return the total sum.

## Sorting and Greedy Choice
This is the most efficient approach. The greedy idea is to always negate the smallest number to achieve the largest possible increase in sum. By sorting the array first, we can efficiently process all the negative numbers. After dealing with them, if we still have operations left (`k > 0`), we can determine the outcome without further simulation by checking the parity of the remaining `k`.
**Time:** O(N log N). The initial sort takes O(N log N). The subsequent passes to flip negatives and find the minimum take O(N) or O(N log N) if re-sorting. The total complexity is dominated by the sorting step. · **Space:** O(log N) or O(N). This depends on the space used by the sorting algorithm implementation. For instance, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N).
**Pros:** Very efficient, with a time complexity dominated by the initial sort.; Intelligently handles large values of `k` by using a parity check instead of simulating every single operation.
**Cons:** The logic is slightly more complex than direct simulation, involving multiple distinct steps (sort, flip negatives, handle remainder).
### Explanation
The key insight is that we should always flip the most negative numbers first. Sorting the array allows us to do this efficiently.
1.  **Sort the array:** This brings all negative numbers to the front, ordered from most negative to least.
2.  **Flip negatives:** Iterate through the sorted array and flip every negative number `nums[i]` to positive, as long as we have operations left (`k > 0`).
3.  **Handle remaining `k`:** After the previous step, all numbers are non-negative, but we might still have `k` operations left. Instead of simulating these, we can use a shortcut. If `k` is even, the net effect is zero. If `k` is odd, it's equivalent to one negation. To maximize the sum, this single negation must be applied to the smallest number in the current array. We find this minimum and flip it.
4.  **Summation:** Calculate the sum of the final array elements.

```java
import java.util.Arrays;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        // Greedily negate the smallest (most negative) numbers first
        for (int i = 0; i < nums.length && k > 0 && nums[i] < 0; i++) {
            nums[i] = -nums[i];
            k--;
        }

        // If k is still positive and odd, we must perform one more negation.
        // To minimize the impact on the sum, we negate the smallest number in the array.
        if (k % 2 == 1) {
            // The array is no longer sorted perfectly after negations (e.g., [-3, -1] -> [3, 1]).
            // We need to find the new minimum.
            Arrays.sort(nums); // Re-sort to easily find the minimum.
            nums[0] = -nums[0];
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}
```
### Algorithm
*   Sort the array `nums` in ascending order.
*   Iterate through the sorted array. As long as the current element `nums[i]` is negative and you have operations left (`k > 0`), negate `nums[i]` and decrement `k`.
*   After the first pass, all the most negative numbers have been flipped to positive. Now, we handle the remaining `k` operations.
*   If the remaining `k` is odd, we must perform one more negation. To maximize the sum (i.e., minimize the loss), we should negate the element with the smallest absolute value. Find the minimum element in the current array (which is now all non-negative) and flip its sign.
*   If the remaining `k` is even, any further operations can be done in pairs (e.g., flip `x` to `-x` and back to `x`), resulting in no net change to the sum. So, we do nothing.
*   Finally, calculate and return the sum of the elements in the modified array.

# Solutions
### Java

```java
class Solution {
public
  int largestSumAfterKNegations(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer : : sum);
    }
    for (int x = -100; x < 0 && k > 0; ++x) {
      if (cnt.getOrDefault(x, 0) > 0) {
        int m = Math.min(cnt.get(x), k);
        cnt.merge(x, -m, Integer : : sum);
        cnt.merge(-x, m, Integer : : sum);
        k -= m;
      }
    }
    if ((k & 1) == 1 && cnt.getOrDefault(0, 0) == 0) {
      for (int x = 1; x <= 100; ++x) {
        if (cnt.getOrDefault(x, 0) > 0) {
          cnt.merge(x, -1, Integer : : sum);
          cnt.merge(-x, 1, Integer : : sum);
          break;
        }
      }
    }
    int ans = 0;
    for (var e : cnt.entrySet()) {
      ans += e.getKey() * e.getValue();
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestSumAfterKNegations(vector<int> &nums, int k) {
    unordered_map<int, int> cnt;
    for (int &x : nums) {
      ++cnt[x];
    }
    for (int x = -100; x < 0 && k > 0; ++x) {
      if (cnt[x]) {
        int m = min(cnt[x], k);
        cnt[x] -= m;
        cnt[-x] += m;
        k -= m;
      }
    }
    if ((k & 1) && !cnt[0]) {
      for (int x = 1; x <= 100; ++x) {
        if (cnt[x]) {
          --cnt[x];
          ++cnt[-x];
          break;
        }
      }
    }
    int ans = 0;
    for (auto &[x, v] : cnt) {
      ans += x * v;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: cnt = Counter(nums) for x in range(- 100, 0): if cnt[x]: m = min(cnt[x], k) cnt[x] -= m cnt[- x] += m k -= m if k == 0: break if k & 1 and cnt[0] == 0: for x in range(1, 101): if cnt[x]: cnt[x] -= 1 cnt[- x] += 1 break return sum(x * v for x, v in cnt . items())

```