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