explaining so that anybody can understand easily| priority queue | beats 100%  time | nlogn +klogk
This is one of the hardest problems that I solved myself!\nPlease upvote if the post helps!\n# Intuition\nlet\'s first start assuming that the given array has a
This is one of the hardest problems that I solved myself!\nPlease upvote if the post helps!\n# Intuition\nlet\'s first start assuming that the given array has all positive numbers, that will make the question easy to understand.\nlook at the subsequence lengthwise of the sorted array\n```\n[]\n\n[1],[2],[3],[4],[5]\n\n[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]\n\n[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]\n\n[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]\n\n[1,2,3,4,5]\n\n```\nNow applying round braces to denote the subsequences that are extension by just one element to the subsequence of length one less. \n```\n[]\n\n([1]),([2]),([3]),([4]),([5])\n\n([1,2],[1,3],[1,4],[1,5]),([2,3],[2,4],[2,5]),([3,4],[3,5]),([4,5])\n\n([1,2,3],[1,2,4],[1,2,5]),([1,3,4],[1,3,5]),([1,4,5]),([2,3,4],[2,3,5]),([2,4,5]),([3,4,5])\n\n([1,2,3,4],[1,2,3,5]),([1,2,4,5]),([1,3,4,5]),([2,3,4,5])\n\n([1,2,3,4,5])\n\n\n\n```\nIf you analyse both the "diagrams", you will realize that all subsequences can be written as prevSubsequence+oneExtraElement.\n\nTwo points that will help you solve the problem now:\n1)adding one element just increases the sum,we go down in such process in the diagram.ALL OF THE DOWN SUBSEQUENCES MUST COME AFTER THE UP SUBSEQUENCES IN THE SUM WEIGHT. \n2)continuing with the same length and going right just increases the sum.ALL OF THE RIGHT SUBSEQUENCES MUST COME AFTER THE LEFT SUBSEQUENCES IN THE SUM WEIGHT.\n\nso for each time we just consider the least sum of the subsequence that is to the right or to the down side!...Why?...technically we should consider all the down and all the right elements but what is the point considering them when only two of them will always come before them in sum.  \n\nSo the last thing to do is to handle negative values, so the maximum sum that we can get is sum of all the positives,now we can just remove positive elements and add the negative elements to get smaller sums ,which is equivalent of removing the smallest sums, so we can use the positive number analysis that we did.\n \n# Approach\n\nWe maintain a priority queue and get the smallest sum, now the next sum has two more candidates, the right and the down,for next priority_queue pop,we consider these candidates too.\n \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nlogn +klogk)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(k)$$\n\n# Code\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>&a, int k) \n    {\n\n        long long totalPositive=0;\n        for(auto &x:a)\n        {\n            if(x<0)x=-x;\n            else totalPositive+=x;\n        }\n        //returning the highest sum possible minus the smallest positive sum  \n        return totalPositive-kPositives(a,k);\n       \n    }\n    long long kPositives(vector<int>&a,int k)\n    {\n        //sorting the array\n        sort(a.begin(),a.end());\n        priority_queue<tuple<long long,int,int>,vector<tuple<long long,int,int>>,greater<>>pq;\n        pq.push({0LL,-1,0});\n        while(--k)\n        {\n            auto [sum,lastIndex,length]=pq.top();\n            pq.pop();\n            //going right\n            if(lastIndex!=-1&&lastIndex+1<a.size())\n            pq.push({sum-a[lastIndex]+a[lastIndex+1],lastIndex+1,length});\n            //going down\n            if(lastIndex+1<a.size())\n            pq.push({sum+a[lastIndex+1],lastIndex+1,length+1});\n    \n        }\n        return get<0>(pq.top());\n    }\n};\n\n```
['Sorting', 'Heap (Priority Queue)']