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

珠玉のプログラミングで取り上げられていた問題を、実際に解いてみる。

問題：
1次元のパターン認識の問題。ｎ要素の浮動小数点の配列ｘを入力とし、配列ｘの連続した要素（部分配列）でその和が最大になるものを見つけて、その和を出力する。

たとえば、
2,-3,6,1,4,2,-5
だったら、出力はx[2..5]の和で13。もっと短くて、
2,-3,6
だったら、出力はx[2]で６。全部、負の数で、
-2,-3,-6
とかだったら、出力は０。

さて、まずは単純に、全部の部分配列の和を求めて比較するアルゴリズム。

#include <iostream>
#include <boost/random.hpp>

using namespace std;
using namespace boost;

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

//部分和を総当たりで調べて、和の最大を求める巻数
float maxSoFar(float x[], size_t length){
	float maxsofar = 0;

	for(int i = 0; i < length; i++){
		for(int j = i; j < length; j++){
			float sum = 0;
			for(int k = i; k < j; k++){
				sum += x[k];
			}
			maxsofar = max(maxsofar, sum);
		}
	}


	return maxsofar;
}

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

		cout << "in " << endl;
		for(int i = 0; i < ARRAY_LENGTH; i++){
			x[i] = rand();
			cout << x[i] << ", " ;
		}
		cout << endl;
	}

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

	return 0;
}

random関数を書くのがめんどくさかったんでboostのを使ってみました。
生成方法はメルセンヌツイスター法をチョイス。
何でも、日本人の方が発明した乱数生成方法で、高速かつ省メモリかつ周期が長いらしいです。