Given a list of integers nums and an integer k, return the k-th largest sum of a contiguous, non-empty subarray. Sums of different subarrays are counted separately even when they are equal: [1, 1] has subarray sums 1, 1, 2, so its 2nd largest sum is 1.
Examples
Input: nums = [2, -1, 3], k = 2
Output: 3
Explanation: subarray sums are 2, -1, 3, 1 (2,-1), 2 (-1,3), 4 (2,-1,3).
In descending order: 4, 3, 2, 2, 1, -1. The 2nd largest is 3.
Input: nums = [1, 1], k = 3
Output: 1
Constraints
1 <= len(nums) <= 500,-10**4 <= nums[i] <= 10**41 <= k <= n * (n + 1) / 2(the number of subarrays)- Target complexity: O(n^2 log k) time and O(k) extra space.
Goals
- Enumerate all contiguous subarray sums with a running total
- Keep only the k largest candidates in a min-heap of size k
- Read the answer off the top of the bounded heap