Profits (UVa Live Archive North America - Southeast - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4869

問題

長さNの数列がある。そのsubstringの総和の最大値を求めよ。
1<=N<=250000

解法

左端から見ていって、総和が負になったら0にもどす。これをしていって最大になった物が答え。