最大子数组和分治与暴力求解法
简单写了求连续子数组的最大和的算法。枚举法时间复杂度为nlgn，暴力法为n^2。但当n比较小的时候，暴力法更为有效，一直很好奇比较小是小到什么程度，故写了程序测试下。
先看暴力求解法
int FindMaxSubArrayViolently(int a[],int high,int &p,int &q)//high为数组a未下标，p与q用应用类型保存最大连续子数组的起始下标与末小标{ int sum_max=-INFINITE,sum; for(int i=0;i sum_max) { sum_max=sum; p=i;q=j; } return sum_max;} 分治法
思路：子数组必然是三种情况之一：
1、在子数组a[low...mid]中
2、在a[mid+1...high]中
3、跨越中点
前两种好解决，将数组a[low...high]二分，递归到当low>=high时返回a[low]为最大连续子数组（只有一个的情况下本身为最大连续子数组）。第三种可以先求得mid点左右两边的最大连续子数组，再相加起来，代码如下：
int FindMaxSubArray(int a[],int low,int high,int &p,int &q){ if (low==high) { p=q=low; return a[low]; } else { int mid=(low+high)/2,left_low,left_high,left_sum,right_low,right_high,right_sum,cross_low,cross_high,cross_sum; left_sum=FindMaxSubArray(a,low,mid,left_low,left_high); right_sum=FindMaxSubArray(a,mid+1,high,right_low,right_high); cross_sum=FindMaxCrossingSubArray(a,low,high,cross_low,cross_high); if(left_sum>=right_sum && left_sum>=cross_sum) { p=left_low;q=left_high; return left_sum; } else if(right_sum>=left_sum && right_sum>=cross_sum) { p=right_low;q=right_high; return right_sum; } else { p=cross_low;q=cross_high; return cross_sum; } }} 求跨越中点时的情况：
int FindMaxCrossingSubArray(int a[],int low,int high,int &p,int &q){ int sum_left,sum_right,sum=0,i,max_left,max_right,mid=(low+high)/2; sum_left=sum_right=-INFINITE; for(i=mid,sum=a[mid];i>=low;sum+=a[--i]) if(sum>sum_left) { sum_left=sum; max_left=i; } for(i=mid+1,sum=a[i];i<=high;sum+=a[++i]) if(sum>sum_right) { sum_right=sum; max_right=i; } p=max_left;q=max_right; return sum_left+sum_right;} 接下来写一个随机数发生器来产生测试数据：
void GenerateRandNum(int a[],int n){ srand(n); for(int i=0;i 再接下来调用windows api来测试时间：
int main(){ DWORD start,end,t1,t2; int a[MAXN],low,high,sum,n=10; t1=t2=0; while(n =t1) { GenerateRandNum(a,n); start=GetTickCount(); sum=FindMaxSubArrayViolently(a,n-1,low,high); end=GetTickCount(); t1=end-start;/*----------------------------------------------------------------*/ GenerateRandNum(a,n); start=GetTickCount(); sum=FindMaxSubArray(a,0,n-1,low,high); end=GetTickCount(); t2=end-start; n+=10; } printf("%d",n); return 0;} 测试结果比我想象的要小，大约n在400~500之间分治法效果就比暴力法好了。