Detailed Explanation using Min Heap (Without any Messy Indices)
Intuition\nClaim We need to negate the minimum element in the array at each step\nProof Observe that negating a positive element make us lose twice the contribu
**Intuition**\n**Claim** We need to negate the minimum element in the array at each step\n**Proof** Observe that negating a positive element make us lose twice the contribution. So if the minimum element is positive,we would lose the least possible contribution by negating it. Also, observe that negating a negative element results in twice the contribution gain in magnitude. So the larger the magnitude of the negative element, the larger the gain.\n```\nclass Solution\n{\npublic:\n    int largestSumAfterKNegations(vector<int>& a, int k);\n};\n\n/* Returns the maximum sum possible after k negations */\nint Solution :: largestSumAfterKNegations(vector<int>& a, int k)\n{\n    // Calculate the initial sum of the array\n    int sum = accumulate(a.begin(), a.end(), 0);\n    \n    // Create a min heap\n    priority_queue<int, vector<int>, greater<int>> minHeap;\n    \n    // Push all the elements onto the min heap\n    for(auto element : a)\n        minHeap.push(element);\n    \n    // Repeat the operation k times\n    for(int i=0; i<k; i++)\n    {\n        // Extract the minimum element\n        int minElement = minHeap.top();\n        minHeap.pop();\n        \n        // Remove the initial contribution and add the negated contribution\n        sum = sum - minElement + (-minElement);\n        \n        // Push the negated element back\n        minHeap.push(-minElement);\n    }\n    \n    return sum;\n}\n```
[]