# KSUBSUM - Editorial

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.

3 Likes

http://www.codechef.com/viewsolution/1761272

@shubham2892 : The number of sub arrays is N(N-1)/2 which is O(N^2) . k1 , k2 , k3 are bounded in this problem . But the total number of sub arrays are not and they can be a huge number like 50000000 for N = 10000 . You will have count variable going up to that . And you are making array access with count variable . That’s the cause of runtime error .

2 Likes

why am i getting a runtime error here

@admin: Can you explain how would you do this-

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.

Using priority queue :

3 Likes

I solved this question using Multiset.But, still there is some doubt.
AC solution: https://www.codechef.com/viewsolution/10907889
TLE solution: https://www.codechef.com/viewsolution/10907825

Both of them is having complexity O(n^2logn).Why one is getting TLE with slight change in approach?

Lets consider the 3rd test case

Given array is 20 -15 10 -15

so cumulativeSum array becomes 20 5 15 0

now till each position of array you will have certain possible sums

1 -> 20

2 -> 5,-15

3 -> 15,-5,0

4 -> 0,-20,-5,-15

Now in your first approach you are putting these elements in the multiset row wise
like 20 then 5 and -15 and so on.

And in your second approach you are putting these elements in the multiset col wise
like 20,5,15,0 and then -15,-5,-29 and so on.

This making your complexity same but as the traversal is different so the number of
times the multiset will be updated is variable.

I see that as the only reason for one getting accepted and other getting tle.

So O(n^2 logn) won’t pass always as stated in the editorial too.

1 Like

Still, i guess the test cases suited my AC approach, because by reversing inner loop we can no way guarantee optimization.Its just sheer luck that my solution passed in O(n^2 logn).

i think O(n^2logn) should not work. According to given constraints unless it is useless

anybody please tell, what’s wrong with my solution.
https://www.codechef.com/viewsolution/22155789

//