Priority Queue || C++
Intuition:    First find the maximum sum possible. We will get maximum possible sum after adding all the elements greater than 0. Next, if we want to find  2nd 
**Intuition**:    First find the maximum sum possible. We will get maximum possible sum after adding all the elements greater than 0. Next, if we want to find  2nd maximum sum what we can do?\nWe can either subtract a smallest positive number from this sum or add largest (minimum(abs(num)) negative number in the sum to get 2nd maximum number.\nSimilarly, we have to add or subtract numbers from current sum to get next largest sum.\n**Key**: We can convert all the negative numbers to positive and then simply can subtract them instead of adding.\nSo to get the maximum sum we will store the least values that needs to be subtracted from maxsum in priority queue (minheap).\nTime O(nlogn + KlogK)\nSpace O(K)\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        int n = nums.size();\n        long long maxsum = 0;\n\t    //subtract stores the sum which needs to be subtracted from the maximum sum\n        vector<long long> subtract;\n        //find the maxsum and update nums so that all elements are positive\n        for(int i=0;i<n;i++){\n            if(nums[i]>=0){\n                maxsum+=nums[i];\n            }else{\n                nums[i] = abs(nums[i]);\n            }\n        }\n        //sorting nums as per absolute values\n        sort(nums.begin(), nums.end());\n        \n        //Initialize priority queue (minheap) to store current least value which needs to be\n        //subtracted from maxsum and the index of nums we are currently at.\n        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;\n        //start from index 0 with minimum value as nums[0]\n        pq.push({nums[0], 0});\n        while(!pq.empty() && subtract.size()<k-1){\n            pair<long long,int> topp = pq.top(); \n            pq.pop();\n            long long subt = topp.first;\n            int idx = topp.second;\n            //push this value to subtract array\n            subtract.push_back(subt);\n            //if we are not at last idx then we can add further values to pq\n            if(idx<n-1){\n                pq.push({subt+nums[idx+1] , idx+1});\n                pq.push({nums[idx+1] + (subt-nums[idx]) , idx+1});\n            }\n        }\n        \n        //ans stores all the largest sum in decreasing order\n        vector<long long>ans;\n        ans.push_back(maxsum);\n        for(long long subt:subtract) {\n            ans.push_back(maxsum - subt);\n        }\n        //return Kth largest sum \n        return ans[k-1];\n    }\n};\n```\n**Similar Problem** which helps to implement priority queue : 373. Find K Pairs with Smallest Sums\n\nUpvote if it helps!!!
['C', 'Heap (Priority Queue)']