C++/Java O(n) | O(1)
Since the A[i] is limited to [-100, 100], we can use an fixed-size array cnt to count occurrences. Bucket sort (or, more precise, countint sort), in other words
Since the ```A[i]``` is limited to [-100, 100], we can use an fixed-size array ```cnt``` to count occurrences. Bucket sort (or, more precise, countint sort), in other words :)\n\nThen, as we process numbers ```[-100, 100]```, we flip the negative numbers by moving count from ```cnt[i + 100]``` to ```cnt[-i + 100]```. This guaranties that, if ```K > 0``` after processing all negative numbers, the first positive number will have the smallest absolute value.\n\nTherefore, when we encounter the first positive number, and our ```K % 2 == 1```, we negate one occurrence of that number.\n```\nint largestSumAfterKNegations(vector<int>& A, int K) {\n  int cnt[201] = {}, j = -100;\n  for (auto i : A) ++cnt[i + 100];\n  for (auto i = -100; i <= 100 && K; ++i) {\n    if (cnt[i + 100]) {\n      auto k = i < 0 ? min(K, cnt[i + 100]) : K % 2;\n      cnt[-i + 100] += k;\n      cnt[i + 100] -= k;\n      K = i < 0 ? K - k : 0;\n    }\n  }\n  return accumulate(begin(cnt), end(cnt), 0, [&](int s, int cnt) { return s + cnt * j++; });\n}\n```\nJava version:\n```\npublic int largestSumAfterKNegations(int[] A, int K) {\n  int[] cnt = new int[201];\n  int res = 0;\n  for (int i : A) ++cnt[i + 100];\n  for (int i = -100; i <= 100 && K > 0; ++i) {\n    if (cnt[i + 100] > 0) {\n      int k = i < 0 ? Math.min(K, cnt[i + 100]) : K % 2;\n      cnt[-i + 100] += k;\n      cnt[i + 100] -= k;\n      K = i < 0 ? K - k : 0;\n    }\n  }\n  for (int i = -100; i <= 100; ++i) res += i * cnt[i + 100];\n  return res;\n}\n```
[]