# 1005. Maximize Sum Of Array After K Negations

Given an array `A` of integers, we **must** modify the array in the following way: we choose an `i` and replace `A[i]` with `-A[i]`, and we repeat this process `K` times in total.  (We 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: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].
```

**Example 2:**

```
Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
```

**Example 3:**

```
Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
```

**Note:**

1. `1 <= A.length <= 10000`
2. `1 <= K <= 10000`
3. `-100 <= A[i] <= 100`

## Thoughts

给定一个数组，将其中K个（可重复选同一个）取反，问和最大能是多少。

1. 和最大要求正数尽量大，负数尽量小。因此先把负数中由小到大取反，如果负数全部取完还不到K, 如果剩下的是奇数，则要把当前所有数中最小值取反
2. 如果最小值是原先负数中的，要减去原来加上的部分，因此是-= min \* 2

## Code

```python
class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        res = 0
        for i, a in enumerate(A):
            if a >= 0 or K == 0: break
            A[i] *= -1
            K -= 1
        return sum(A) if K % 2 == 0 else sum(A) + -2 * min(A) 
```

```cpp
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int res = 0, c = 0; 
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] < 0 && c < K) {
                A[i] *= -1;
                res += A[i];
                ++c;
            }
        }
        if ((K - c) % 2 == 1) {
            if (c >= 1 && A[c - 1] < A[c]) {
                // when the min is a pre-negative element, minus the preadded val.
                res -= A[c - 1] * 2;
                res += A[c];
            } else {
                res -= A[c];
            }
        } 

        if ((K - c) % 2 == 0) c -= 1;
        for (int i = c + 1; i < A.size(); ++i) {
            res += A[i];
        }
        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/sorting/maximize-sum-of-array-after-k-negations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.