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.