Hi friends,can anyone suggest away of doing the following problem in O(n) time using DP. 327A - Flipping Game
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi friends,can anyone suggest away of doing the following problem in O(n) time using DP. 327A - Flipping Game
Name |
---|
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?