Merge sorted lists
This problem is more or less similar to the "Merge sorted lists" problem. https://leetcode.com/problems/merge-k-sorted-lists/\n\nSay the nums array is [1,2,3,4,
This problem is more or less similar to the "Merge sorted lists" problem. https://leetcode.com/problems/merge-k-sorted-lists/\n\nSay the `nums` array is `[1,2,3,4,5]`, then we have 5 sorted lists (desending order) for the subsequence sums:\n\n```\nsum-1, sum-1-2, sum-1-2-3, sum-1-2-3-4, sum-1-2-3-4-5\nsum-2, sum-2-3, sum-2-3-4, sum-2-3-4-5\nsum-3, sum-3-4, sum-3-4-5\nsum-4, sum-4-5\nsum-5\n```\n\nNow, in order to find the kth largest subsequence sum, we just need to use a heap to merge the sorted lists.\n\nFor me, the tricky part of this problem is that the input array contains both positive and negative numbers, and we need to combine them using abs.\n\nThe code is simpler because we don\'t really need to initialize the heap with 5 numbers.\n\n```\n    /*\n    Runtime: 95 ms, faster than 100.00% of Java online submissions for Find the K-Sum of an Array.\n    Memory Usage: 87.6 MB, less than 33.33% of Java online submissions for Find the K-Sum of an Array.\n     */\n    public long kSum(int[] nums, int k) {\n        int[] abs = new int[nums.length];\n        long max = 0;\n\n        for (int i = 0; i < nums.length; i++) {\n            if (nums[i] >= 0) {\n                abs[i] = nums[i];\n                max += nums[i];\n            } else {\n                abs[i] = -nums[i];\n            }\n        }\n\n        if (k == 1) {\n            return max;\n        }\n\n        Arrays.sort(abs);\n\n        Queue<long[]> queue = new PriorityQueue<>(Comparator.comparingLong(l -> -l[0]));\n        queue.add(new long[] {max - abs[0], 0});\n\n        while (k > 2) {\n            long[] curr = queue.poll();\n\n            if (curr[1] + 1 < abs.length) {\n                queue.add(new long[] {curr[0] + abs[(int) curr[1]] - abs[(int) (curr[1] + 1)], curr[1] + 1});\n                queue.add(new long[] {curr[0] - abs[(int) (curr[1] + 1)], curr[1] + 1});\n            }\n\n            k--;\n        }\n\n        return queue.poll()[0];\n    }\n```
[]