分治法求最大子列和

题目如标题，题目用到了分而治之的算法思想，以下是分而治之的定义：

这是自己大一暑假写的逐次遍历的方法

时间复杂度是O(n²)

#include<stdio.h>
#define MAX 100000
int main()
{
	int i,j,n,maxSum,tempSum,a[MAX];//定义数组大小的新方法，即通过宏定义 
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	maxSum=0;
	for(i=0;i<n;i++)
	{
		tempSum=0;//保证每个初始值为0 
		for(j=i;j<n;j++)//循环不止有计数功能，有数组时，一定要注意下标 
			{
				tempSum+=a[j];
				if(tempSum>maxSum)//核心问题：可以算一步，判断一步 
					maxSum=tempSum;
			}
	}
	printf("%d",maxSum);	
		
}

以下是分而治之的方法

T ( N ) =O( N log N )
int MaxSum(int a[],int left,int right);
int threeOfMax(int a1,int a2,int a3);
int centerMaxSum(int a[],int left,int right);

```c

#include<stdio.h>
#define N 50
int MaxSum(int a[],int left,int right);
int centerMaxSum(int a[],int left,int right);
int threeOfMax(int a1,int a2,int a3);
int main(){
 int n;
 int a[N];
    printf("请设置数组位数n：\n");
 scanf("%d",&n);
 printf("请输入数值：\n");
 for(int i = 0;i<n;i++){
  scanf("%d",&a[i]);
 }
 int left=0;
 int right=n-1; 
 int maxSubSum = MaxSum(a,left,right);
 printf("最大子序列的和为:%d\n",maxSubSum);
 return 0;
} 
 
int MaxSum(int a[],int left,int right){
 int a1,a2,a3,i;
 int MaxLeftSum, MaxRightSum; //存放左右子问题的解
    int MaxLeftBorderSum, MaxRightBorderSum; //存放跨分界线的结果
 
    int LeftBorderSum, RightBorderSum;
 // 递归终止条件 直到分到最后一个元素 
 if(left==right){
   if( a[left] > 0 )
            return a[left];
        else
            return 0;
 }
 int mid = (left+right)/2;
 // 划分左边
 a1 = MaxSum(a,left,mid);
 // 划分右边
 a2 = MaxSum(a,mid+1,right);
 // 求解s3 
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for( i=mid; i>=left; i-- )   //从中线向左扫描
    {
        LeftBorderSum += a[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } //左边扫描结束
 
    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for( i=mid+1; i<=right; i++ )   //从中线向右扫描
    {
        RightBorderSum += a[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } //右边扫描结束 
    a3 =centerMaxSum(a,left,right);;
    //下面返回"治"的结果
    return threeOfMax( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
 
}
// 求解s3 
int centerMaxSum(int a[],int left,int right){
 int leftSum = 0;
 int rightSum = 0;
    int templeftSum = 0;
 int temprightSum = 0;
 int mid=(left+right)/2;
 for(int i = mid;i>=left;i--){
  templeftSum = templeftSum+a[i];
  if(templeftSum>leftSum)
  leftSum=templeftSum; 
 }
 for(int j = mid+1;j<=right;j++){
  temprightSum = temprightSum+a[j];
  if(temprightSum>rightSum)
  rightSum=temprightSum;
 }
 
 return leftSum+rightSum;
}
 
// 求解最大的子列和 
int threeOfMax(int a1,int a2,int a3){
	int maxSum = a1>a2?a1:a2;
	return maxSum>a3?maxSum:a3;
}

摘自