| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hello all. I was solving one problem which boils down to finding 2 numbers (precisely their indices) in an array which are at least some distance k apart such that their sum is maximum. How can i solve this problem in O(n).
eg indice 1 2 3 4 5 6 7 8 9 10 arr[i] 4 18 18 20 11 17 17 14 14 17
given k = 3; answer is : 4(20) , 7(17).
What you can do is have an array that stores the maximum value seen so far in arr and a second array that stores the index of that maximum value. So for the given example the arrays would look like:
Max: {4, 18, 18, 20, 20, 20, 20, 20, 20, 20}
Index: {0, 1, 1, 3, 3, 3, 3, 3, 3, 3}
And then for every element in the array greater than or equal to k (0-based indexing), if arr[i] + max[i-k] is greater than the current max, store the indices i and index[i-k] as your current answer.
Thank you, Ahmad. I kind of get you but still not very convinced why this works?
Since the array keeps track of the largest element so far at some position x, for every number in the array you can figure out what partner would be optimal for it by looking at the index array (since that stores the index of the largest seen value) at postition i-k (it needs to be at least k away from i). So with that you can find the optimal partners for each number and then take the maximum pairing.