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.
