k-th largest sum of continuous subseq of an array

Revision en1, by hoang25, 2021-08-25 22:50:01

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?

Thanks in advance!

Tags problems, prefixsums

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hoang25 2021-08-25 22:50:01 360 Initial revision (published)