# LeetCode 1005: Maximize Sum Of Array After K Negations

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

In one operation, we choose an index and negate the value at that index.

We must perform exactly `k` operations.

We need to return the maximum possible sum of the array after exactly `k` negations.

The official constraints state that `1 <= nums.length <= 10^4`, `-100 <= nums[i] <= 100`, and `1 <= k <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `nums` and integer `k` |
| Output | Maximum sum after exactly `k` negations |
| Operation | Negate any element, must do exactly `k` times |

Function shape:

```python
def largestSumAfterKNegations(nums: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [4, 2, 3]
k = 1
```

Negate `2`:

```python
[4, -2, 3] -> sum = 5
```

Or negate `3`:

```python
[4, 2, -3] -> sum = 3
```

All numbers are positive and we must use exactly one negation. To lose as little sum as possible, negate the number with the smallest absolute value: `2`.

That gives:

```python
[4, -2, 3]
```

The sum is `5`, which is the maximum possible after exactly one negation.

Answer:

```python
5
```

Example 2:

```python
nums = [3, -1, 0, 2]
k = 3
```

Negate `-1` → `[3, 1, 0, 2]`, then we have 2 more negations. Use remaining on `0` twice. Sum = `3 + 1 + 0 + 2 = 6`.

Answer:

```python
6
```

Example 3:

```python
nums = [2, -3, -1, 5, -4]
k = 2
```

Negate `-3` and `-4`: `[2, 3, -1, 5, 4]`. Sum = `2 + 3 + (-1) + 5 + 4 = 13`.

Answer:

```python
13
```

## Key Insight

Greedy approach:

1. Negate the most negative numbers first (they become positive, increasing the sum the most).
2. If `k` negations remain after all negatives are turned positive, and `k` is odd, negate the smallest absolute value element once (to minimize the loss).

## Algorithm

1. Sort `nums` numerically so negative numbers appear first.
2. For each element from smallest to largest: if negative and `k > 0`, negate it and decrement `k`.
3. After all negatives are handled, if `k` is odd, negate the element with the smallest absolute value.
4. Return the sum.

More precisely:
1. Sort `nums`.
2. Negate elements from smallest (most negative) while they are negative and `k > 0`.
3. If `k` is still odd, negate the element with minimum absolute value.
4. Return sum.

## Correctness

Negating the most negative elements first always increases the sum by the maximum amount per operation.

Once all negatives are handled, any remaining operations on positive numbers will decrease the sum. To minimize this loss, negate the element with the smallest absolute value. If an even number of operations remain, we can negate the same element twice (net zero effect).

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` | Sort in place |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
        nums.sort()

        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1

        if k % 2 == 1:
            nums.sort()
            nums[0] = -nums[0]

        return sum(nums)
```

## Code Explanation

Sort and negate negatives from smallest to largest:

```python
nums.sort()
for i in range(len(nums)):
    if nums[i] < 0 and k > 0:
        nums[i] = -nums[i]
        k -= 1
```

If `k` is still odd, find the element with smallest absolute value and negate it:

```python
if k % 2 == 1:
    nums.sort()
    nums[0] = -nums[0]
```

We re-sort because after negating negatives, the smallest element (by value) is now at the beginning.

Return the sum:

```python
return sum(nums)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.largestSumAfterKNegations([4, 2, 3], 1) == 5
    assert s.largestSumAfterKNegations([3, -1, 0, 2], 3) == 6
    assert s.largestSumAfterKNegations([2, -3, -1, 5, -4], 2) == 13
    assert s.largestSumAfterKNegations([-2, -3], 2) == 5
    assert s.largestSumAfterKNegations([1], 1) == -1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[4,2,3]`, `k=1` | `5` | Negate smallest positive |
| `[3,-1,0,2]`, `k=3` | `6` | Negate `-1` then use extra `k` on `0` |
| `[2,-3,-1,5,-4]`, `k=2` | `13` | Negate two negatives |
| `[-2,-3]`, `k=2` | `5` | Both negatives become positive |
| `[1]`, `k=1` | `-1` | Must negate the only element |