| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
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!
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))$$$.
Bin search th answer and uisng segtree and prefix sum to check i guest =))
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
If 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.
Can you explain your sliding-window method? What constant subarray size are you taking?
Ah, sorry, I meant two pointers, not sliding window.