[Java] Priority Queue with Thought Process and Explanation
Thought Process\nWe can start by considering what the first few largest subsequence sums are by going through an example. Let\'s take the array [-4, -3, -2, -1,
**Thought Process**\nWe can start by considering what the first few largest subsequence sums are by going through an example. Let\'s take the array `[-4, -3, -2, -1, 2, 5]` as our example.\n\nFor `k == 1`, i.e. the largest subsequence sum, we should be able to see fairly quickly that in general this is just the sum of all the positive integers. For our example, this is `5 + 2 = 7`. Let\'s call this number `maxSubsequenceSum`.\n\nFor `k == 2`, the next largest subsequence sum will come from applying the smallest "change" we can make from our previous subsequence sum. We should be able to see that a "change" means that we either need to add a negative number or remove a positive number. Clearly, the smallest change we can make is choosing either the smallest positive number or the smallest (in absolute value) negative number. For our example, let\'s find the smallest "change" we can make. Two of the candidates are adding -1 or removing 2, but clearly adding -1 is smaller, so the next largest subsequence sum is `5 + 2 - 1 = 6`. Notice that removing the smallest positive number or adding the smallest (in absolute value) negative number are essentially doing the same thing, which is just substracting the smallest absolute value from the previous subsequence sum. So, the easiest way to find the smallest "change" is to sort the absolute values of the array and choose the smallest value. If the smallest absolute value is positive, the "change" would be to remove the positive number. If the smallest absolute value is negative, the "change" would be to add the negative number. Therefore, once we have a sorted absolute value array of `nums`, let\'s call this `abs`, the next largest subsequence sum just amounts to doing `maxSubsequenceSum - abs[0]`. \n\nFor `k == 3`, we have more choices to consider. We could potentially do the same process as the previous largest subsequence sum in which we find the smallest "change" we can make and apply it. However, notice that this actually isn\'t the next largest subsequence sum, as instead of applying the next smallest "change", we can just replace the last "change" we made with the next smallest "change". For our example, this would be adding the -2 or removing the 2, so replacing our previous "change" of adding -1 would either be adding -2 to get `5 + 2 - 2 = 5` or removing 2 to just get `5`. As we saw before, these are the exact same in code, which amount to doing `maxSubsequenceSum - abs[1]`.\n\nFor `k == 4`, we could potentially use what we tried for `k == 3`, which is to combine the smallest two "changes", however there is another possibility here as well. The third smallest "change" could be smaller than the combination of the two smallest "changes". For our example, the third smallest change is actually removing the 2 (or adding -2, since one of these was done for `k == 3` we can use the other here), giving us just `5`. This amounts to doing `maxSubsequenceSum - abs[2]`. However, in general we aren\'t sure if this is larger or if `maxSubsequenceSum - abs[0] - abs[1]` is larger.\n\nFrom `k == 4` onward, we see that the formula for the subsequence sum isn\'t as simple, since we aren\'t sure which combination of "changes" would be larger. However, we can see that in general, if we cannot use "changes" from lower indices, the next largest subsequence sum would be would be to replace the current "change" with the next smallest "change". For example, the next largest subsequence sum from `maxSubsequenceSum - abs[1]` would be `maxSubsequenceSum - abs[2]` if we disallow using the "change" at index 0. If we didn\'t disallow using the "change" at index 0, we saw before that we aren\'t sure in general if `maxSubsequenceSum - abs[0] - abs[1]` is larger. But we are guaranteed that one of these is the value for `k == 4` since using `abs[3]` is guaranteed to be a larger (or equal) "change" since the array is sorted.\n\nSo, when considering the next largest subsequence sums, we need to consider both possibilities: either keep the last "change" and continue it or replace the last "change" with the next smallest "change". For example, from `maxSubsequenceSum - abs[0]`, we can either continue it with `maxSubsequenceSum - abs[0] - abs[1]` or replace it with `maxSubsequenceSum - abs[1]`. In the continuation possibility, we continue using the "change" at index 0, but in the replacement possibility, we disallow using the "change" at index 1. So `maxSubsequenceSum - abs[1]` would branch out with `maxSubsequenceSum - abs[1] - abs[2]` and `maxSubsequenceSum - abs[2]`. This way, we ensure that we cover all possibilities for the next few largest subsequence sums.\n\nWe also want to explore next largest subsequence sums in order, which motivates us to use a max heap / priority queue structure. From a certain subsequence sum, we will put both possibilities into the heap and keep track of the last "change" that we applied. By using a heap, we can ensure that the top of the heap is the next largest subsequence sum, so we can then pop from the heap in order and continue to explore possibilities.\n\n**Code**\n```\nclass Solution {\n    public long kSum(int[] nums, int k) {\n        // Calculate maxSubsequenceSum and abs.\n        long maxSubsequenceSum = 0;\n        int[] abs = new int[nums.length];\n        for (int i = 0; i < nums.length; ++i) {\n            int num = nums[i];\n            if (num > 0) {\n                maxSubsequenceSum += num;\n            }\n            abs[i] = Math.abs(num);\n        }\n        Arrays.sort(abs);\n        \n        // Max heap to maintain the largest subsequence sums. \n\t\t// The first number in the pair is the subsequence sum. \n\t\t// The second number is the index of the last "change" we made to obtain this subsequence sum.\n        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((p1, p2) -> {\n            return Long.compare(p2.getKey(), p1.getKey()); \n        });\n        \n        // List of subsequence sums in order.\n        ArrayList<Long> subsequenceSums = new ArrayList<>();\n        subsequenceSums.add(maxSubsequenceSum);\n        \n        // Start with the smallest "change" we can make.\n        pq.add(new Pair(maxSubsequenceSum - abs[0], 0));\n        while (subsequenceSums.size() < k) {\n            // Get previous largest subsequence sum and add it to list.\n            Pair<Long, Integer> subsequenceSum = pq.poll();\n            long lastSubsequenceSum = subsequenceSum.getKey();\n            int lastChange = subsequenceSum.getValue();\n            subsequenceSums.add(lastSubsequenceSum);\n            \n            if (lastChange < nums.length - 1) {\n                // Continue with the last "change"\n                pq.add(new Pair(lastSubsequenceSum - abs[lastChange + 1], lastChange + 1));\n                // Replace the last "change"\n                pq.add(new Pair(lastSubsequenceSum + abs[lastChange] - abs[lastChange + 1], lastChange + 1));\n            }\n        }\n        \n        return subsequenceSums.get(k - 1);\n    }\n}\n```
['Heap (Priority Queue)', 'Java']