8.4

ある配列に含まれる,全ての部分配列の中で,
[要素の合計値が最大になる部分配列]の要素の合計値を求める.

以下は本文中で紹介されているアルゴリズム.
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);
}

こんなに簡単にできるんですね.
ちょっと感動した.