蓝桥杯算法提高VIP-和最大子序列 （C++代码）分治法！ 类似归并排序的思路！ 非常详细！

解题思路: 1.以中间的元素为界限，把子串划分为三种情况：一。左边到中间，二。右边到末尾  这两种可以递归解决！   三。中间的左右都有一部分，然后相加。
注意事项:
        第三种情况必须用临时的左右和存储值，不然会出错
参考代码:

#include<iostream>
using namespace std;
const int maxsize=100001;
int N;
int MaxSum(int a[],int left,int right){
int s1,s2,s,sum=0,midsum=0,m,lsum=0,rsum=0;
int l=left,r=right;
int ls,rs;//临时存放第三种情况左右序列的和 
if(l==r)
  sum=a[l];
  else {
  m=(r-l)/2+l;
  lsum=MaxSum(a,l,m);//第一种情况  左边到中间的和 
  rsum=MaxSum(a,m+1,r); //第二种情况  中间到右边的和 
  //第三种情况的话分左右子序列
    s1=0,ls=0;
   for(int i=m;i>=l;i--){
      ls+=a[i];     //寻找左边子序列最大和 
      if(ls>s1) s1=ls;
   }
     s2=0,rs=0;
     for(int j=m+1;j<=r;j++){
     rs+=a[j];    //寻找右边子序列最大和 
     if(rs>s2)  s2=rs;
     }
     midsum=s1+s2;
   if(midsum>lsum)
    sum=midsum;
    else sum=lsum;
    if(sum<rsum)
    sum=rsum;  }
  return sum;
}
int main(){
int A[maxsize];
   cin>>N;
   for(int i=0;i<N;i++)
   cin>>A[i];
   cout<<MaxSum(A,0,N-1);
return 0;}