C++ || Priority Queue || Explained
Approach:\n\n we need to find the kth largest subsequence sum\n the array consist of both +ve and -ve numbers\n the subsequence with maxsum will be the one with
**Approach:**\n\n* we need to find the kth largest subsequence sum\n* the array consist of both +ve and -ve numbers\n* the subsequence with maxsum will be the one with all the non-neg values\n* now, the 2nd maxsum subsequence will either be\n\t* ``` maxsum- min_pos_value```\n\t* ```maxsum + max_neg_value``` (remember that -2>-10) or we can say ```maxsum- min_abs_neg_value```\n* so we find the maxsum first\n* then update all the neg values to their abs values and sort the array\n* now, we make a maxheap to store the {current max sum, index}\n* we run the loop till the size of our ans array is <k\n* now let\'s say we have the currSum as curr and the index as i\n* now the next maxSum can be\n\t* subtract the next min element from the sorted_nums\n\t\t* ```pq.push({curr - nums[i + 1], i + 1});```\n\t* get back to the previous maxSum and instead of subtracting the ith element subtract the (i+1)th element\n\t\t* ```pq.push({curr - nums[i + 1] + nums[i], i + 1});```\n* example:\n\t\t* sorted nums = {1,2,3,4,10,12}\n\t\t* maxsum = 12+4+3+1 = 20\n\t\t* push {20-1,0}\n\t\t* now,\n\t\t\t* curr=19, i=0\n\t\t\t* store 19 in the ans\n\t\t\t* next possible max sum can be:\n\t\t\t\t* 19-2 i.e ```curr-nums[i+1]```\n\t\t\t\t* or \n\t\t\t\t* 20-2 i.e ```curr+nums[i]-nums[i+1]```\n* return the kth subsequence sum i.e ans[k-1]\n\n**Code:**\n\n```\nclass Solution\n{\npublic:\n    typedef pair<long long, long long> pi;\n    long long kSum(vector<int> &nums, int k)\n    {\n        int n = nums.size();\n        priority_queue<pi> pq; //{sum,index}\n        long long maxsum = 0;\n        for (auto &x : nums)\n            (x >= 0) ? maxsum += x : x *= -1;\n\n        sort(nums.begin(), nums.end());\n        pq.push({maxsum - nums[0], 0});\n        vector<long long> ans;\n        ans.push_back(maxsum);\n\n        while (ans.size() < k)\n        {\n            auto [curr, i] = pq.top();\n            pq.pop();\n            ans.push_back(curr);\n            if (i + 1 < n)\n            {\n                pq.push({curr - nums[i + 1], i + 1});\n                pq.push({curr - nums[i + 1] + nums[i], i + 1});\n            }\n        }\n        return ans[k - 1];\n    }\n};\n```
['C', 'Heap (Priority Queue)', 'C++']