第八章 高效算法设计

分治法求最大连续和

注意范围是[x,y)

#include<bits/stdc++.h>
using namespace std;
int maxsum(int *A,int x,int y){

    if(y-x==1) return A[x];
    int m=x+(y-x)/2;
    int maxs = max(maxsum(A,x,m),maxsum(A,m,y));
    int v,L,R;
    v=0; L=A[m-1];
    for(int i=m-1;i>=x;i--) L=max(L,v+=A[i]);
    v=0; R=A[m];
    for(int i=m;i<y;i++) R=max(R,v+=A[i]);
    return max(maxs, L+R);
}
int main()
{
    int A[]={1,-1,2,3,-2};
    printf("%d\n",maxsum(A,0,4));
    return 0;
}
#include<bits/stdc+