QuickSelect O(n) solution
We don\'t need sorted sequence. We just need the K smallest negative elements to negate their sign and if we have less than K negative elements  and the left nu
We don\'t need sorted sequence. We just need the K smallest negative elements to negate their sign and if we have less than K negative elements  and the left number of operations is odd - choose the smallest positive (or zero) and negate its sign.\n```\n    int largestSumAfterKNegations(vector<int>& A, int K) {\n\n        nth_element(A.begin(), A.begin() + K, A.end());\n        int cnt = K;\n        int minIdx = 0;\n        \n        for (int i = 0; i < K; ++i) {\n            if (A[i] < 0) {\n                A[i] = -A[i];\n                cnt--;\n            }\n            if (A[i] < A[minIdx]) minIdx = i;\n        }\n        if (cnt % 2 != 0) {\n            A[minIdx] = -A[minIdx];\n        }\n        \n        return accumulate(A.begin(), A.end(), 0);\n    }\n```
[]