【大学院入試044】龍谷大学大学院

\(n\)を正の整数とする．長さ\(n\)の整数列\(a_1\)，\(a_2\)，\(a_3\)，\(\ldots\)，\(a_n\)に対して，第\(i\)項から第\(j\)項までの部分和

　　\(\displaystyle S_{i,j}=\sum_{k=i}^j a_k\)

の最大値を求めたい．ただし，\(1 \leq i \leq j \leq n\)である．例えば，\(n=8\)で，\(a_1=5\)，\(a_2=-6\)，\(a_3=4\)，\(a_4=-1\)，\(a_5=-2\)，\(a_6=6\)，\(a_7=-7\)，\(a_8=5\)のとき，\(S_{i,j}\)の最大値は\(7\)である（\(i=3\)，\(j=6\)のとき）．これをどのような手順で行えばよいかを考え，その手順を説明しなさい．

★なるべく効率的な手順を示したい★