算法学习之分治策略-最大子数组

/*算法学习之分治策略-最大子数组*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct result_t
{
	int sum;
	int start;
	int end;
};
struct result_t find_mid_arry(int *a,int start,int mid,int end)
{
	struct result_t left;
	struct result_t right;
	struct result_t cross;
    int i,sum;

	left.sum = -10000;
	sum = 0;
	left.end=mid;

    for(i=mid;i>=start;i--) {
		sum+=a[i];
		if(sum>=left.sum) {
			left.sum = sum;
			left.start = i;
		}
	}
	right.sum = -10000;
	sum = 0;
	right.start = mid+1;
	for(i=mid+1;i<=end;i++) {
		sum+=a[i];
		if(sum>=right.sum) {
			right.sum = sum;
			right.end = i;
		}
	}
	cross.start = left.start;
	cross.end = right.end;
	cross.sum = left.sum+right.sum;
	return cross;
}
/*此递归函数是一个典型的二路递归,可以用一个完全二叉树表示递归过程
                           n
               n/2                   n/2
		n/4           n/4	   n/4          n/4
		.              .        .            .
		.              .        .            .
        .              .        .            .
		
    可以用树的后序遍历顺序表示递归顺序 要在自己的大脑中想象出一个很深的栈然后把函数的压栈顺序理清楚
	i表示进栈 o表示出栈
	按数组大小为10进行进出栈顺序为 f(0,9)i->f(0,4)i->f(0,2)i->f(0,1)i->f(0,1)o->f(1,2)i->f(1,2)o->f(0,2)o->f(3,4)i->f(3,4)o->f(0,4)o，到这整个数组左半部
	进出栈递归已经完成，然后开始右半部，右半部同上.
	以上模拟出了一个典型的二路递归的流程所以算法复杂度为此完全二叉树的深度lgn乘以叶子节点n=nlgn,暴力法的复杂度为n2,当数组长度超过10000后其速度将不能忍受
	对于递归程序要有很好的抽象思维和整体把握的概念
*/
struct result_t find_max_arry(int *a,int start,int end)
{
    struct result_t left;
	struct result_t right;
	struct result_t cross;
	struct result_t r;
	int mid;
	if((mid=(start+end)/2)==start) {
		r.start = r.end = start;
		r.sum = a[start];
		return r;
	} else {
		left = find_max_arry(a,start,mid);  //递归查找子数组左半边最大值
		right = find_max_arry(a,mid+1,end); //递归查找子数组右半边最大值
		cross = find_mid_arry(a,start,mid,end); //合并查找数组中间最大值
		/*以下是返回到上一层数组左半边或右半边的最大值*/
		if(left.sum>=cross.sum&&left.sum>=right.sum) {
			return left;
		}
		else if(right.sum>=cross.sum&&right.sum>=left.sum) {
			return right;
		}
		else
			return cross;
	}
}
int main()
{
	int a[]={-1,-2,2,3,4,5,6,-7,8,-9};
	struct result_t result;
	result = find_max_arry(a,0,9);
	printf("%d",result.sum);
	return 0;
}