hoang25's blog

k-th largest sum of continuous subseq of an array
By hoang25, history, 3 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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))$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bin search th answer and uisng segtree and prefix sum to check i guest =))

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 solution
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your sliding-window method? What constant subarray size are you taking?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, sorry, I meant two pointers, not sliding window.

      → Reply