### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Given an array A of N integers, we are asked to find the Kth maximum sum of a contiguous subarray of elements. Finding the Maximum sum of a subarray is a well known problem. If the array elements are all non-negative, we can use binary search to find the answer in O(n log S) time, where S is the maximum sum of a subarray. In this problem, the values can be negative. As with the other problems in this set, look at the constraints carefully, N ≤ 10,000 and K ≤ 2012. We go through the array from left to right and at each index i, we find all K maximum sums of subarrays, ending at index i. If S is the prefix sum array, where S[i] = A1 + A2 + … + A[i], then all subarray sums ending at index i can be computed using S[i] - S[j], for j = 0 to i-1 and considering S[0] = 0. But we only need top K of them, so we can subtract S[j] s in non-decreasing order and only K of them. This requires us to maintain the array S in sorted order and this can be done similar to insertion sort in O(K) time per insertion.

Now that we have the top-K subarray sums ending at index i, we can compare them with the current top-K best answers so far and pick some of them and drop others. Note that at each step you only need to maintain K minimum prefix sums and K maximum subarray sums so far. Given the best K sums so far and the current K sums, we can merge the two sorted arrays and get the updated best K sums. This can also be done in O(K) time. The overall time complexity is O(NK). Maintaining a set ( or heap ) in which each insertion is additional O(log K) only increases the running time by more than 10x and may not fit in the given time limit.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.