You are not logged in. Please login at www.codechef.com to post your questions!

×

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] = A[1] + A[2] + ... + 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.

This question is marked "community wiki".

asked 22 Nov '12, 12:09

0★admin ♦♦
19.0k348495533
accept rate: 37%

12 Answers:
 3 @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 . answered 01 Feb '13, 11:48 12.4k●47●107●170 accept rate: 12%
 2 Using priority queue : http://ideone.com/GoaPY4 answered 23 Jun '16, 16:36 11 accept rate: 0%
 2 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. answered 26 Jul '16, 15:07 46●2 accept rate: 25%
 0 i am getting runtime error..please help.. http://www.codechef.com/viewsolution/1761272 answered 01 Feb '13, 01:32 1 accept rate: 0%
 0 "If the array elements are all non-negative, we can use binary search to find the answer in O(n log S) time" I'm new to this approach how exactly are u thinking of doing it using binary search pls share.. thanx answered 17 Jul '13, 23:20 2★h1t35h 1●2 accept rate: 0%
 0 Answer is hidden as author is suspended. Click here to view. answered 31 May '15, 10:00 3★vsanjay (suspended) accept rate: 10%
 0 @admin: Can you please explain how would you do this- Blockquote 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. answered 05 Jan '16, 21:33 3★disisbig 1●1 accept rate: 0%
 0 @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. answered 05 Jan '16, 21:36 3★disisbig 1●1 accept rate: 0%
 0 You can sort the array in non-decreasing order. The entire array gives the max sum. Exclude the first element, this gives you 2nd largest sum. Exclude the 2nd element, this gives you third largest sum and so on. Assumption : Sorting algorithm takes O(nlogn) time. answered 23 Jun '16, 15:33 11 accept rate: 0%
 0 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? answered 26 Jul '16, 04:57 297●9 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,482
×3,212
×5
×1

question asked: 22 Nov '12, 12:09

question was seen: 9,156 times

last updated: 19 Mar, 19:36