最大部分配列問題をc言語で実装してみる

全探索での実装

下記のように2重ループ処理をして、全探索をします。
全ての組み合わせの合計値を順次算出して、最大値を更新していきます。
getMax()については、別途関数として実装しています。
サンプルコードを参照してください。
計算量はo(n^2)になりますね。

int getMaxSubArray_fullSearch(int* array, int size){
	int i, j;
	int maxSum = 0, sum = 0;
	
	//２重ループ処理をして全探索
	for(i = 0; i < size; i++){
		for(j = i; j < size; j++){
			sum += array[j];//連続した配列の要素の合計値を算出
			maxSum = getMax(maxSum, sum);//ここで最大値を逐次更新
		}
		sum = 0;
	}
	
	return maxSum;
}

kadaneアルゴリズム

参考：[c言語]ナップザック問題を動的計画法でコーディング
最大部分配列問題の解法としては、kadaneアルゴリズムが有名ですね。
DP(Dynamic programming)ですね。
一重ループで0番目からインクリメントしていき、現在位置より手前の連続した部分配列の最大値を更新していきます。
更に、全体での部分配列の最大値を更新していきます。
計算量はo(n)になり、全探索に比べてぐっと計算量が削減できます。

int getMaxSubArray_kadaneAlgo(int* array, int size){
	int i;
	int maxSum = 0, sum = 0;
	
	for(i = 0; i < size; i++){
		//現在位置より手前の連続した部分配列の最大値を更新
		sum = getMax(array[i], sum + array[i]);
		maxSum = getMax(maxSum, sum);//ここで全体の最大値を逐次更新
	}

	return maxSum;	
}

サンプルコード

下記がサンプルコードになります。
いくつかの配列のパターンで試してみました。
（一つ以外はコメントアウトしています。）

$ cat sample.c 
#include <stdio.h>

int getMax(a, b){
	if(a > b){
		return a;
	}else{
		return b;
	}
}

int getMaxSubArray_fullSearch(int* array, int size){
	int i, j;
	int maxSum = 0, sum = 0;
	
	for(i = 0; i < size; i++){
		for(j = i; j < size; j++){
			sum += array[j];
			maxSum = getMax(maxSum, sum);
		}
		sum = 0;
	}
	
	return maxSum;
}

int getMaxSubArray_kadaneAlgo(int* array, int size){
	int i;
	int maxSum = 0, sum = 0;
	
	for(i = 0; i < size; i++){
		sum = getMax(array[i], sum + array[i]);
		maxSum = getMax(maxSum, sum);
	}

	return maxSum;	
}

int main(){
	int ret = 0;
	//int array01[] = {1, 4, 5, -6, 2, 7};
	//int array01[] = {1, 4, 5, -10, -6, 2, 7, -1, -3};
	//int array01[] = {1, 4, 5, -10, -6, 2, 7, 8, -1, -3};
	//int array01[] = {4, -6, 2, -11};
	//int array01[] = {-9, 2};
	int array01[] = {1, 4, 5,-10,  -6, 2, 7, -1, -3, -4, -10, 2, 3, 5, 9};
	int size = (int)(sizeof(array01) / sizeof(array01[0]));
	
	ret = getMaxSubArray_fullSearch(array01, size);
	printf("maxSum=%d\n", ret);

	ret = getMaxSubArray_kadaneAlgo(array01, size);
	printf("maxSum=%d\n", ret);
	
	return 0;
}

$ gcc -o sample sample.c
$ ./sample 
maxSum=19
maxSum=19