k-th largest sum of continuous subseq of an array

Правка en1, от 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?