Heap with candidate values
Intuition\n\nThe largest sum is obviously the sum of all positive elements of the array. For the $k$-th largest sum we have to remove some of the positive terms
# Intuition\n\nThe largest sum is obviously the sum of all positive elements of the array. For the $k$-th largest sum we have to remove some of the positive terms from this maximal sum and probably add some negative terms. So it has the form:\n\n$$\n    \\sum_{i: a_i>0} a_i - \\sum_{j \\in S} |a_j|\n$$\nNow the problem is actually find the $k$-th smallest sum for the the array of absolute values. For a subset of indices $S$ denote $a_S=\\sum_{i\\in S} a_i$ the corresponding sum.\n\nSuppose now that the numbers in the array are  sorted in **non-decreasing** order.  Introduce a partial order on the subset of indices. The ``key\'\' function is $S\\mapsto (a_S, \\max S)$. That is $S\'< S\'\'$ if $a_{S\'}< a_{S\'\'}$ or $a_{S\'}= a_{S\'\'}$  and $\\max S\' < \\max S\'\'$.\n\nWe want to enumerate the subsets of indices according to this ordering. The first element of the sequence is $S_0=\\emptyset$.\n\nSuppose that we already have $S_0\\leq \\cdots\\leq S_k$. $S_{k+1}$ is one of the smallest element not in $\\{S_0, \\dots, S_k\\}$.\n\nLet $x+1=\\max S_{k+1}$ and  $S\' = (S_{k+1}\\setminus\\{x+1\\})\\cup\\{x\\}$. That is we replace the largest element $x+1$ of $S_{k+1}$ with $x$.\n\n$S\'< S_{k+1}$ so it is one of $S_0, S_1, \\dots, S_k$. If it is $S_j$ then the largest element of $S_j$ is $x$ and $S_{k+1}$ is either $(S_j\\setminus\\{x\\})\\cup \\{x+1\\}$ or $S_j\\cup\\{x+1\\}$.\n\nIn order to generate the first $k$ element of $(S_j)$ we can  keep the possible values in a heap and when $S_k$ is obtained update the set of possible values. Of course $S_k$ is not interesting at the end only $a_{S_k}$.  \n\nIn the implementation, $(a_S, 1+\\max S)$ is stored in the heap.\n\n\n# Complexity\n- Time complexity: $$O(n(\\log k))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ndef kth_smallest_sum(k, nums):\n    \n    values = [(0, 0)]\n    k -= 1\n    nums = heapq.nsmallest(k, nums)\n    while k > 0:\n        k -= 1\n        s, i = heapq.heappop(values)\n        if i < len(nums):\n            heapq.heappush(values, (s+nums[i], i+1))\n            if i > 0:\n                heapq.heappush(values, (s+nums[i]-nums[i-1], i+1))\n    \n    return values[0][0]\n\nclass Solution:\n    def kSum(self, nums: List[int], k: int) -> int:\n        max_sum = sum(num for num in nums if num >0)\n        return max_sum - kth_smallest_sum(k, (num if num >= 0 else -num for num in nums))\n\n```
['Python3']