https://uva.onlinejudge.org/external/110/11078.pdf
Please go through the link..
How can i solve this problem with linear scan. O(n^2) solution is very obvious to me. But linear scan solution o(n), i have no idea,Please help?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 164 |
| 2 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 154 |
| 5 | maroonrk | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.05.2024 08:21:28 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
While scanning from left to right in the array, just keep a variable 'maxi' storing the maximum value you have encountered so far and at the current step you are sure that whatever 'maxi' is storing is the maximum value amongst all the senior of current candidate and just calculate this difference and find the maximum among all these differences.
please can someone, help me understand the above illustrated case?
When i = 1, maxi = 0, curnum = 4, now maxi becomes 4, When i = 2, maxi = 4, curnum = 3, update ans to 4 — 3 = 1; When i = 3, maxi = 4, curnum = 2, update ans to 4 — 2 = 2; When i = 4, maxi = 4, curnum = 1, update ans to 4 — 1 = 3; [Assuming 1-indexing].
I have a question. If the complexity is O(n^2) and given the constraints, the problem should be accepted. or I am wrong?