Description Link to heading

1005.maximize-sum-of-array-after-k-negations

Solution Link to heading

Greedy algorithm.

Code Link to heading

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // first step
        for (int i = 0; i < A.size(); i++) { // second step
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // third step
        int result = 0;
        for (int a : A) result += a;        // forth step
        return result;
    }
};