Hi friends,can anyone suggest away of doing the following problem in O(n) time using DP. 327A - Flipping Game
Hi friends,can anyone suggest away of doing the following problem in O(n) time using DP. 327A - Flipping Game
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 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 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
A solution was posted in this editorial. The algorithm the author is referring to at the end of his solution is called Kadane's Algorithm. You can find an explanation here.
I don't understand why are you asking when there is an editorial? Is it so hard to click on the tutorial button on the right of the problem statement? And BTW, this is one of the few good and detailed editorials on codeforces.
Because my O(n) submission using Kadane's algo is giving wrong answer! :) 10026842
Then you should have mentioned that in your post, shouldn't you?