O(n + k logn) using min-heap
1.build a min-heap (cost O(n));\n2.negate the root node\'s val then heapify the heap\nrepeat step 2  K times\n\n\nclass Solution {\npublic:\n    \n    void heap
1.build a min-heap (cost O(n));\n2.negate the root node\'s val then heapify the heap\nrepeat step 2  K times\n\n```\nclass Solution {\npublic:\n    \n    void heapify(int arr[], int n, int i) { \n        int smallest = i;  \n        int l = 2*i + 1; // left = 2*i + 1 \n        int r = 2*i + 2; // right = 2*i + 2 \n        if (l < n && arr[l] < arr[smallest]) smallest = l; \n        if (r < n && arr[r] < arr[smallest]) smallest = r; \n        if (smallest != i) { \n            swap(arr[i], arr[smallest]); \n            heapify(arr, n, smallest); \n        } \n    } \n  \n    void helper(int arr[], int n, int K) { \n        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);   \n        for(int i = 0; i < K; ++i) {\n            arr[0] = -arr[0];\n            heapify(arr, n, 0);\n        }\n    } \n    int largestSumAfterKNegations(vector<int>& A, int K) {\n        if(A.empty()) return -1;\n        int sum = 0;\n        helper(A.data(), A.size(), K);\n        for(auto &e:A) sum += e;\n        return sum;\n    }\n    \n};\n```
['Heap (Priority Queue)', 'C++']