> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/sorting/maximize-sum-of-array-after-k-negations.md).

# 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;
    }
};
```