ある配列に含まれる,全ての部分配列の中で,
[要素の合計値が最大になる部分配列]の要素の合計値を求める.
以下は本文中で紹介されているアルゴリズム.
O(n)で動作します.
int find_max(int * xs, int N){
int currmax=0;
int maxval=0;
for(int i=0; i<N; i++){
currmax = max(currmax+xs[i],0);
maxval = max(maxval, currmax);
}
return (maxval);
}
こんなに簡単にできるんですね.
ちょっと感動した.