Java | heap
java\nclass Solution {\n    public long kSum(int[] nums, int k) {\n        //1. the max value will be the sum of all the positives\n        //2. sums of every s
```java\nclass Solution {\n    public long kSum(int[] nums, int k) {\n        //1. the max value will be the sum of all the positives\n        //2. sums of every subsequence can be derived by removing positives from or adding negetives to the max value\n        //3. we can turn every negetive into its absolute value, \n        //   so "max - abs(neg)" means we add negetives to the max-value subsequence.\n        //  "max - pos" means we remove positives from the max-value subsequence.\n        //4. we transform original question into "finding the (k-1)th smallest sum of subsequence"\n        //      eg: the 1th largest subsequnce will be "max - 0"\n        //          the 2th largest subsequnce will be "max - 1th smallest sum of subsequence"\n        //5. to get the kth smallest sum of subsequence in nlogn, \n        //   we will try to iterate sum of subsequnce in increasing order,\n        //   then use a heap to store them\n        //6. for an increasing array [a, b, c], we can choose draw a tree to interate it\n        //          a\n        //        /    \\\n        //     b         a+b\n        //    / \\       /   \\\n        //   c   b+c   a+c   a+b+c\n        //7. interate in this way and find the (k-1)th smallest sum of subsequnce using heap\n        //   answer will be max - (k-1)th smallest sum of subsequence\n        \n        \n        long max = 0;\n        for (int i = 0; i < nums.length; i ++) {\n            if (nums[i] > 0)\n                max += nums[i];\n            else\n                nums[i] = -nums[i];\n        }\n        Arrays.sort(nums);\n        PriorityQueue<long[]> que = new PriorityQueue<>((n1, n2) -> (Long.compare(n1[0], n2[0])));\n        que.offer(new long[]{nums[0], 0});\n\n        long kmin = 0;\n        for (int i = 1; i < k; i ++) {\n            long[] node = que.poll();\n            kmin = node[0];\n            if (node[1] == nums.length - 1)\n                continue;\n            que.offer(new long[] {kmin + nums[(int)node[1]+1], node[1]+1});\n            que.offer(new long[] {kmin - nums[(int)node[1]] + nums[(int)node[1]+1], node[1]+1});\n        }\n        \n        return max - kmin;\n    }\n}\n```
['Heap (Priority Queue)']