はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

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に載っていた他のアルゴリズムも実装してみたいです。
あとあれですね。英語を読んで新たなことを学ぶと、なんか頭良いことしてるなって感じますね。以上です。