1005. Maximize Sum Of Array After K Negations

https://leetcode.com/problems/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

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) 

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