hoang25's blog

By hoang25, history, 5 months ago, Hello guys, I'm having trouble with a problem.

Given an array A and a number k, find the k-th largest continuous subsequence! I can only think of a brute-force solution using prefix sum, which run in O(n ^ 2). In this problem n could be as large as 1e5. Can anyone give me a hint?  Comments (5)
 » 5 months ago, # | ← Rev. 2 →   Binary search for the answer. Let the answer be x, you can find in $O(nlog(n))$ time how many elements are greater than or less than that sum using prefix sum. Total complexity $O(n*log(n)*log(sum))$.
 » 5 months ago, # | ← Rev. 2 →   As kindly pointer out by Farhan132, the approach below is terribly wrong. Maybe it could be useful as an exercise to find mistakes in others' solutions :D As they say, there is always a fast, but wrong solutionIf it is just positive numbers, there is a faster option -- two-pointers technique while keeping a multiset of $k$ largest sums so far. When extending or shrinking the window: if the multiset is less than $k$, just add the current window sum, otherwise check if it falls between the maximum and minimum value of the multiset, and if it is -- just add it to the multiset and remove the minimum from it. This will be $O(nlog(k))$, so it wouldn't depend on the overall sum — plus could be faster if $k$ is small.