[C++] Priority Queue Solution with Explanation
Idea:\n1. Find the largest summation of this array, which is sum of all positive numbers.\n2. There are two types of operation to get next number:\n\ta. Remove 
Idea:\n1. Find the largest summation of this array, which is sum of all positive numbers.\n2. There are two types of operation to get next number:\n\ta. Remove one positive number from largest number.\n\tb. Add a new negtive number\n3. Repeat step2 k times.\n```c++\n/*\nTake [2, 4, -3] as example\nmax: 6 (2 + 4)\na. Remove one positive number from largest number: 6 - 2 = 4\nb. Add a new negtive number: 6 + (-3) = 3\n*/\n```\nIf we convert all positive number in nums to negative, and sort it.\nStep 2.a and 2.b can be consider to the same operation.\n```c++\n/*\noriginal array: [2, 4, -3]\nconverted and sorted array: [-2, -3, -4]\nThe following list all combinations.\n6 = 6                                      // 2 + 4\n6 + (-2) = 4                               // 4\n6 + (-3) = 3                               // 2 + 4 + (-3)\n6 + (-4) = 2                               // 2\n6 + (-2) + (-3) = 1                        // 4 + (-3)\n6 + (-2) + (-4) = 0                        // x\n6 + (-3) + (-4) = -1                       // 2 + (-3)\n6 + (-2) + (-3) + (-4) = -3                // -3\n*/\n```\nWe can see there are 2^3 = 8 conditions. (all subsets of the sorted array)\nBut we don\'t need to list all subset and sort it to get kth item.\n\nWe can use priority queue instead.\nIn each time we pop from priority queue\nWe add two new elements:\n1. Add next number\n2. Remove current number and add next number\n\n```c++\n/*\n0.\npush {4, 0} // 6 + nums[0]\n1. \n* pop {4, 0} // 6 + nums[0]\n* push {1, 1} // 6 + nums[0] + nums[1]\n* push {3, 1} // 6 + nums[1]\n2. \n* pop {3, 1}\n3. ...\n*/\n```\n\n\n```c++\ntypedef pair<long long, int> pli;\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        int n = nums.size();\n        long long maxSum = 0;\n        for (long long i=0; i<n; ++i) {\n            if (nums[i] > 0) {\n                maxSum += nums[i];\n                nums[i] *= -1;\n            }\n        }\n        \n        long long res = maxSum;\n        sort(nums.begin(), nums.end(), greater<int>());\n        \n        priority_queue<pli> pq;\n        pq.push({maxSum + nums[0], 0});\n        \n        for (int i=0; i<k-1; ++i) {\n            auto [val, idx] = pq.top(); pq.pop();\n            res = val;\n            if (idx+1 < n) {\n                pq.push({val - nums[idx] + nums[idx+1], idx+1});\n                pq.push({val + nums[idx+1], idx+1});\n            }\n        }\n        \n        return res;\n    }\n};\n```
['C']