Decreasing Subsequence Sums
This problem needs some serious unpacking.\n\n#### 1. Sort the Array\nEven though the description says:\n\n> A subsequence is an array that can be derived from 
This problem needs some serious unpacking.\n\n#### 1. Sort the Array\nEven though the description says:\n\n> A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.\n\n...sum is a commutative operation, and we can rearrange elements as we please. Thus, we will sort elements, as it is  essential for the next step.\n\n#### 2. K-th Smallest Subsequence Sum\nThere is a similar problem - [1918. Kth Smallest Subarray Sum](https://leetcode.com/problems/kth-smallest-subarray-sum/), but it\'s for subarrays (not subsequences).\n\nOn some other platforms, I found a heap-based solution, which generates next sums as we go, which is more appropriate for this problem.\n\nGenerating all possible subarrays is extremely time-consuming. Note that `k` is small, and it gives us a hint that we should generate increasing sum subarrays as we go.\n\nThis algorithm is very cool, and it requires the array to be sorted. We use a min heap, where we store the current sum **and** the index of the last element in the subsequence.\n\nWe start with one element with the index 0 (which gives us the smallest sum). For each step:\n1. We pop `sum`, and index `i` from the min heap (smallest sum so far).\n2. We push two new sums to the heap (and increase index `i`):\n\t- `sum + nums[i + 1]`\n\t- `sum + nums[i + 1] - nums[i]`.\n\nFor the `[1, 2, 3, 4]` example, we have the following subarrays (and their representation in the heap).\n- `[1]`: `{1, 0}`\n\t- `[1, 2]`: `{3, 1}`\n\t\t- `[1, 2, 3]`: `{6, 2}`\n\t\t\t- `[1, 2, 3, 4]`: `{10, 3}`\n\t\t\t- `[1, 2, 4]`: `{7, 3}`\n\t\t- `[1, 3]`: `{4, 2}`\n\t\t\t- `[1, 3, 4]`: `{8, 3}`\n\t\t\t- `[1, 4]`: `{5, 3}`\n\t- `[2]`: `{2, 1}`\n\t\t- `[2, 3]`: `{5, 2}`\n\t\t\t- `[2, 3, 4]`: `{9, 3}`\n\t\t\t- `[2, 4]`: `{6, 3}`\n\t\t- `[3]`: `{3,2}`\n\t\t\t- `[3, 4]`: `{7, 3}`\n\t\t\t- `[4]`: `{4, 3}`\n\nWe get these increasing sums as we pop elements from the heap: `1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10`.\n\n#### 3. K-th Largest Sum\nFor this problem, we will start with the sum of all elements, and then subtract increasing subsequence sums (generated using the above approach).\n\nFor the above example, the initial sum is 10 (`[1, 2, 3, 4]`). The next sum is 9 (`[2, 3, 4]`), then 8 (`[1, 3, 4]`), and so on.\n\nOf course, we need to use max heap instead of min heap.\n\n#### 4. Handling Negatives\nThe initial maximum sum should include all positive elements. \n\nExcluding a positive element from the subsequence is not much different than including a negative element - both operations decrease the sum.\n\nTherefore, we sort the array by absolute values, and also decrease the sum by `abs(nums[i + 1])`.\n\n**C++**\n```cpp\nlong long kSum(vector<int>& nums, int k) {\n    sort(begin(nums), end(nums), [](int a, int b){ return abs(a) < abs(b); });\n    long long res = accumulate(begin(nums), end(nums), 0LL, [](long long sum, int n){ return sum + max(0, n); });\n    priority_queue<pair<long long, int>> pq;\n    pq.push({res - abs(nums[0]), 0});\n    while(--k) {\n        auto [sum, i] = pq.top(); pq.pop();\n        if (i + 1 < nums.size()) {\n            pq.push({sum - abs(nums[i + 1]), i + 1});\n            pq.push({sum + abs(nums[i]) - abs(nums[i + 1]), i + 1});\n        }\n        res = sum;\n    }\n    return res;\n}\n```
['C']