Volume0-0022 Maximum Sum Sequence

問題
最大連続部分和 | Aizu Online Judge

配列の最大連続部分和を求める問題です。
動的計画法で出来ないかな～と考えましたが、僕の脳みそでは全探索しか思いつきません。
色々と調べると、何やら参考になりそうなものを発見。
qiita.com

一番最後に書かれている「Kadane's algorithm」が動的計画法っぽく、O(n)なので、これを実装することにしました。
とはいうものの、コードの内容がよく分からない…という訳で「Kadane's algorithm」でググりました。そんでたどり着いたのがコチラ。
codeforces.com

ここに載ってるトレースでなんとなく理解できた気がします。

MaxSoFar　…　i番目までで作れる部分配列の最大値（これをnまで計算したものが答え）
MaxEndingHere　…　部分配列の左端からi番目までの和（途中結果みたいなイメージ）
i番目の値をMaxEndingHereに加算し、
(i)　MaxEndingHere > MaxSoFar　⇒　MaxSoFarを更新（最高得点！）
(ii)　MaxSoFar > MaxEndingHere > 0　⇒（この先の要素を足せば最大になる可能性があるので）何もしない
(iii)　MaxEndingHere < 0　⇒　（今後何を足しても最大値になりえないので）0にする（部分配列の左端をリセットする）
ってのを0～n-1まで繰り返します。

#include<stdio.h>
#define MAX 5000

int main(){

 int n,i,j;
 int A[MAX];
 int MaxEndingHere;
 int MaxSoFar;

 while(1)
 {

  scanf("%d",&n);
  if(n==0)break;
  MaxEndingHere=0;
  MaxSoFar=-10000000;


  for(i=0;i<n;i++)
  {
    scanf("%d",&A[i]);

    MaxEndingHere+=A[i];
    if(MaxEndingHere > MaxSoFar)MaxSoFar=MaxEndingHere;
    if(MaxEndingHere < 0)MaxEndingHere=0;

  }

  printf("%d\n",MaxSoFar);

 }

return 0;
}

こうやってブログを書くことで、更に理解が深まった気がします。いつかqiitaに載っていた他のアルゴリズムも実装してみたいです。
あとあれですね。英語を読んで新たなことを学ぶと、なんか頭良いことしてるなって感じますね。以上です。