Beats 100% time, Solution with Explanation
Intuition\n\n- For an example let\'s take an array [-5, -3,-2, 1, 7], the largest sum that can be formed from a subsequence is 8. when k = 1, the answer is obvi
# Intuition\n\n- For an example let\'s take an array [-5, -3,-2, 1, 7], the largest sum that can be formed from a subsequence is 8. when k = 1, the answer is obviously 10.\n- If k = 2, the second largest subsequence sum is supposed to be returned. In this case we can add(if negative) or subtract(if positive) the lowest number of array. So the second largest subsequence sum will be 7 - 1 = 6.\n- If k = 3, the third largest subsequence sum is supposed to be returned. In this case 6 +(-2) = 4, which is not correct because adding -2 with the largest subsequence(8) sum gives 6. and further for k = 4, adding -3 with 8 gives 5.\n- This shows that the previous subsequence sums are supposed to be considered before adding or subtracting the minimum number.\n- So the code should have two cases for every number as (sum-Currnumber) and (sum-currNumber+prevNumber) which means (6-2) and (6-2+1).\n\n# Explanation:\n\n- Find the maximum sum subsequence of the input array and store it in variable max(simply the sum of all positive numbers).\n- Adding a negative number and subtracting the positive number, both means the same, that is subtracting from the max. So negative numbers are unsigned.\n- In the function a min heap is declared and initialized with the first number for sum and its index for tarcking the previous number.\n- A variable curr is declared and used for returning(if curr == k) the sum that needs to be deducted from max.\n- Both the cases as explained in intuition are added to the heap.\n- The returned value is deducted from max to kth min is found.\n\n\n\n\n\n# Code\n```\nclass Solution {\n    class Pair {\n        long sum;\n        int tail;\n        Pair(long sum, int tail) {\n            this.sum = sum;\n            this.tail = tail;\n        }\n    }\n    public long kSum(int[] nums, int k) {\n        int n = nums.length;\n        long max = 0L;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] < 0) nums[i] = -nums[i];\n            else max += nums[i];\n        }\n        Arrays.sort(nums);\n        long kmin = getKthSubset(nums, k);\n        return max - kmin;\n    }\n    private long getKthSubset(int[] nums, int k) {\n        int n = nums.length;\n        PriorityQueue<Pair> minHeap = new PriorityQueue<>((a, b) -> Long.compare(a.sum, b.sum));\n        int cur = 1;\n        minHeap.add(new Pair(nums[0], 0));\n        while (cur < k) {\n            Pair min = minHeap.poll();\n            long sum = min.sum;\n            int next = min.tail + 1;\n            cur++;\n            if (cur == k) return sum;\n            if (next < n) {\n                minHeap.add(new Pair(sum + nums[next], next));\n                minHeap.add(new Pair(sum + nums[next]- nums[min.tail], next));\n            }           \n        }\n        return 0L;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']