分治算法求最大最小值c语言 [蓝桥杯][算法提高VIP]和最大子序列 （C语言代码）分治法...

解题思路:

注意事项:

参考代码:#include

#include

#include

#include

#include

#include

usingnamespacestd;

constintmaxn=100001;

inta[maxn];

intmaxsum(int*A,intx,inty)//返回左闭右开区间[x,y)中的最大连续和

{

intv,L,R,maxs;

if(y-x==1)returnA[x];

intm=x+(y-x)/2;//划分

maxs=max(maxsum(A,x,m),maxsum(A,m,y));

v=0;

L=A[m-1];

for(inti=m-1;i>=x;--i)//合并

{

L=max(L,v+=A[i]);

}

v=0;

R=A[m];

for(inti=m;i

{

R=max(R,v+=A[i]);

}

returnmax(maxs,L+R);

}

intmain()

{

intT;

scanf("%d",&T);

for(inti=0;i

{

scanf("%d",&a[i]);

}

printf("%d\n",maxsum(a,0,T));

return0;

}