AOJ 0022 （Maximum Sum Sequence : 和の最大値）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0022

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022

【解説】

数列\(a_n\)の連続する部分和の最大値を求める問題。負の数の取り扱いがポイントとなる。

基本的には前から順番に正負関係なく項を加算していき、その中での最大値を求めればよい。ただし、加算していく中で\(a_i\)までの合計が負となった場合は、\(a_1～a_i\)までの項を使用せず、\(a_{i+1}\)から新たに加算していく方が明らかに最大値が大きくなるため、その場合は\(a_i\)までの合計を0として、以降の加算処理を行っていけばよい。

【コード】