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

昨日のアルゴリズムからループ一つ減らしたもの。

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

using namespace std;
using namespace boost;

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

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

	for(int i = 0; i < length; i++){
		float sum = 0;
		for(int j = i; j < length; j++){
			sum += x[j];
			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;
	}

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

	return 0;
}

そいだけじゃ、なんなので、「分割して統治」アルゴリズム版も

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

using namespace std;
using namespace boost;

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

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

//和の最大を求める関数：分割して統治のアルゴリズム
float maxsum3(float x[], int l, int u){
	if(l > u){//要素がない場合
		return 0.0f;
	}

	if(l == u){
		return max(0.0f, x[l]);
	}

	int m = (l + u) / 2;

	//境界から左に伸びる部分配列の和最大値
	float lmax, rmax, sum;
	lmax = sum = 0.0f;
	for(int i = m; i >= l; i--){
		sum += x[i];
		lmax = max(lmax, sum);
	}

	//境界から右に伸びる部分配列の和最大値
	rmax = sum = 0.0f;
	for(int i = m + 1; i <= u; i++){
		sum += x[i];
		rmax = max(rmax, sum);
	}
	
	return max(lmax + rmax, maxsum3(x, l, m), maxsum3(x, m+1, u));
}




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 = maxsum3(x, 0, ARRAY_LENGTH - 1);//計算
		cout << maxsofar << endl;//答え出力
	}

	return 0;
}

配列の長さはアルゴリズムによってテキトーに変えています。これは、後半に紹介するアルゴリズムほど計算が早く終わってしまい、テキトーなストップウォッチでは、計測不能(０秒)になってしまうからです。

分割して統治のアルゴリズムを簡単に説明します。
配列を真ん中から２つに分けます。
すると、元の配列の最大部分和は、頭側の配列の最大部分和か、尾側の配列の最大部分和か、2つにまたがった部分配列の和か、のいずれかになります。
これを再帰的に行うことで、元の配列の最大部分和を求めることができます。

言葉だけだと、わかりにくいですね。すいません。詳しくは「珠玉のプログラミング」を参考にしていただければと思います。