問題概要
あるバスがあり，ある時点で非負の人数が乗っていた．その時点からのバスの乗降記録が与えられる．乗降記録は数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ の形で与えられ，$A_i$ は $i$ 箇所目の停留所で乗客が $A_i$ 人増えた（負の場合はその絶対値分減った）ことを表す．
乗降記録に矛盾しない（i.e., 乗客数が負にならない），記録終了時のバスの乗客数としてあり得る最小値はいくらか？
制約
- $1 \leq n \leq 2 \times 10^5$
- $-10^9 \leq A_i \leq 10^9$
解法
何か基準が無いと難しいので，初期状態からの変化分について考えることにします．$A$ の添字を時刻だと捉えると，時刻 $i$ の乗降が終わった時点での乗客の数は，時刻 $i - 1$ での乗客の数に $A_i$ を足した値となります．初期状態の乗客数を $0$ と仮置きし，時刻 $i$ での乗客数を $P_i$ と書くことにすれば，$P$ は漸化式
\begin{equation*}
P_i = \begin{cases}
0 & \text{($i = 0)$} \\
P_{ i - 1 } + A_i & \text{(otherwise)}
\end{cases}
\end{equation*}
によって求まります（このような列は（競プロ文脈では？）「累積和」と呼ばれ，しばしば有用です）．$P_i$ はある時刻での乗客数の初期状態からの変化量を表しています．もし $P$ の最小値 $\min P$ が負だったとすれば，初期の乗客数を $0$ と仮置きしたのは少なすぎたということになり，負にならないように調整する必要があります．最小限の調整幅はどれだけかというと，$P$ 全体が $-( \min P )$ だけ正方向にズレればよく，その場合の最終的な乗客数は $P_n - \min P$ となります．
この解法の場合，累積和とその最小値の計算に $\Theta( n )$ 時間がかかります．そもそも入力に $\Theta( n )$ 時間かかるので，これでよいです．
実装について
C++ では，累積和の計算に std::partial_sum が使えます．先頭に $0$ が欲しいので，
vector< int > p( 1 );
と用意しておいて std::back_inserter で挿入してあげるといい感じになります．
Haskell では scanl が使えて，
scanl (+) 0 as
で終わりです．
コード (C++)
int main() { IN( int, N ); VLL A( N ); cin >> A; VLL psum( 1 ); partial_sum( ALL( A ), BI( psum ) ); cout << psum.back() - *min_element( ALL( psum ) ) << endl; return 0; }
コード (Haskell)
main = do getLine as <- readIntegers let psum = scanl (+) 0 as mi = minimum psum print $ last psum - mi
