分治法及暴力法求解数组中连续最大子数组及分别占用运行时间比较：

分治法：nlgn

暴力法：n*n

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#include <string.h>

#define NEGATIVE_INFINITY -1000

typedef struct RESULT{
	int low;
	int high;
	int sum;
}Result;


void findmaxsubarraybydivide(int *arr,int low,int high,Result *p_result);
void findmaxsubarraybymid(int *arr,int low,int mid,int high,Result *p_result);
void findmaxsubarraybyviolence(int *arr,int low,int high,Result *p_result);
int getsubsum(int *arr,int low,int high);


/*
*分治法求最大子数组 
*arr:目标数组，low:初始索引，high:结束索引，p_result:保存子数组结果的指针
*/
void findmaxsubarraybydivide(int *arr,int low,int high,Result *p_result){
	Result left,right,mid;
	if(low == high){	//分解到最底层，只有一个基本元素时
		p_result->low = low;
		p_result->high = high;
		p_result->sum = arr[low];
	}else{
		//左侧最大子数组
		findmaxsubarraybydivide(arr,low,(low+high)/2,p_result);
		memcpy(&left,p_result,sizeof(Result));

		//右边最大子数组
		findmaxsubarraybydivide(arr,(low+high)/2 + 1,high,p_result);
		memcpy(&right,p_result,sizeof(Result));

		//跨越中点的最大子数组
		findmaxsubarraybymid(arr,low,(low+high)/2,high,p_result);
		memcpy(&mid,p_result,sizeof(Result));

		/*返回最大连续子数组*/
		if(left.sum >= right.sum && left.sum >= mid.sum){
			memcpy(p_result,&left,sizeof(Result));
		}else if(mid.sum >= left.sum && mid.sum >= right.sum){
			memcpy(p_result,&mid,sizeof(Result));
		}else{
			memcpy(p_result,&right,sizeof(Result));
		}
	}
}

/* 跨越中点的最大子数组(分治法)
*arr:目标数组，low:初始索引，mid:中间索引，high:结束索引
*/
void findmaxsubarraybymid(int *arr,int low,int mid,int high,Result *p_result){
	int i;
	int sum=0;
	int tmpsum;
	p_result->sum = NEGATIVE_INFINITY;
	p_result->low = mid;
	p_result->high = mid;
	for(i= mid;i>=low;i--){	//由中间向低索引展开寻找最大连续数组
		sum += arr[i];
		if(p_result->sum < sum){
			p_result->sum = sum;
			p_result->low = i;
		}
	}

	sum = 0;
	tmpsum = p_result->sum;
	for(i=mid+1;i<=high;i++){	//由中间向高索引展开寻找最大连续数组
		sum += arr[i];
		if(p_result->sum < sum + tmpsum){
			p_result->sum = sum + tmpsum;
			p_result->high = i;
		}
	}
}

/*暴力法求解最大子数组
*arr:目标数组，low:初始索引，high:结束索引
*/
void findmaxsubarraybyviolence(int *arr,int low,int high,Result *p_result){
	int i,j;
	int n = high - low + 1;
	int sum;
	p_result->sum = NEGATIVE_INFINITY;
	for(i=1;i<n+1;i++){		//子数组长度为i时
		for(j=0;j<=n-i;j++){	//长度为i的子数组共有n-i+1个
			sum = getsubsum(arr,low+j,low+j+i-1);//获取长度为i的子数组和
			if(sum > p_result->sum){
				p_result->sum = sum;
				p_result->low = low+j;
				p_result->high = low+j+i-1;
			}
		}
	}
}
/*求子数组和(暴力法)
*arr:目标数组，low:初始索引，high:结束索引
*返回子数组的和
*/
int getsubsum(int *arr,int low,int high){
	int i,sum=0;
	for(i=low;i<=high;i++){
		sum +=arr[i];
	}
	return sum;
}

int main(int argc,char* argv[]){
	LARGE_INTEGER frequency;
	LARGE_INTEGER start;
	LARGE_INTEGER end;

	Result result;
	int array[100];			//原数组
	int i;

	srand(time(NULL));
	for(i=0;i<100;i++){
		array[i] = ((rand())%201 - 100)%101;	//生成-100到100之间的数
		if(i%5 == 0)
			printf("\n");
		printf("%d,",array[i]);
	}
	printf("\n--------\n");


	if(!QueryPerformanceFrequency(&frequency))	//获取cpu频数计数器
		return -1;
	QueryPerformanceCounter(&start);	//获取初始次数
	
	findmaxsubarraybydivide(array,0,99,&result);		//分治法
	//p_result = findmaxsubarraybyviolence(array,0,99);	//暴力破解法

	QueryPerformanceCounter(&end);		//获取结束次数
	//程序运行时间
	printf("分治法运行时间:%f\n",(double)(end.QuadPart-start.QuadPart)/(double)frequency.QuadPart);
	printf("子数组下标low:%d,high:%d,sum:%d\n",result.low,result.high,result.sum);
	
	QueryPerformanceCounter(&start);
	findmaxsubarraybyviolence(array,0,99,&result);
	QueryPerformanceCounter(&end);
	printf("\n\n");
	printf("暴力法运行时间:%f\n",(double)(end.QuadPart-start.QuadPart)/(double)frequency.QuadPart);
	printf("子数组下标low:%d,high:%d,sum:%d\n",result.low,result.high,result.sum);
	return 0;
}