部分配列で、その和が最大になるものを求める〜その４〜

最後に、走査アルゴリズムというのを実装してみました。
例によって詳細は「珠玉のプログラミング」に載っているのですが、簡単に説明すると、

x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和か、x[n]から左方向に伸びた配列の和のいずれかである。
という考えにもとづいたものです。

これを利用して解くのが、次に示す走査アルゴリズムのコードです。

#include <iostream>
#include <boost/random.hpp>
#include "autoStopWatch.h"

using namespace std;
using namespace boost;

const int ARRAY_LENGTH = 1000000;
float x[ARRAY_LENGTH];

float max(float f1, float f2, float f3){
	return max(f1, max(f2, f3));
}

//和の最大を求める関数：走査アルゴリズム
float maxSoFar(float x[], int length){
	float maxsofar = 0;
	float maxendinghere = 0;

	for(int i = 0; i < length; i++){
		maxendinghere = max(0.0f, maxendinghere + x[i]);
		maxsofar = max(maxsofar, maxendinghere);
	}
	
	return maxsofar;
}


int main(){
	//ランダムな配列生成
	{
		mt19937 gen;
		uniform_real<float> dst(-100, 100);
		variate_generator<mt19937, uniform_real<float> > rand(gen, dst);

		for(int i = 0; i < ARRAY_LENGTH; i++){
			x[i] = rand();
		}
	}

	{
		AutoStopWatch sw;
		float maxsofar = maxSoFar(x, ARRAY_LENGTH);//計算
		cout << maxsofar << endl;//答え出力
	}

	return 0;
}

これまた、テキトーに時間測定してます。
自分のコードで、正確な処理時間比較はしていないけれども、
配列の要素数がすんごい大きいものを取り扱った場合、最初のアルゴリズムで41年かかる計算が、最後のアルゴリズムだと48ミリ秒で計算できるそうな。すごひ！
アルゴリズムによって、こんなにも計算速度が変わるものなんかと、びっくりした。