最大连续和

用一般暴力方法：

best = a[i]//初始化最大值
for(int i = 1;i <= n;i++)
for(int j = i;j <= n;j++){
int sum=0;                //检查连续子序列a[i] + ... ... + a[j]
for(int k = i;k <= j;k++)
sum += a[k];              //累加元素和
if(sum > best) best = sum;//更新最大值
}

优化时间复杂度为 $O(n^{2})$

s[0]=0;//s存前缀和
for(int i = 1; i <= n; i++)s[i]=s[i-1]+a[i];
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
best = max(best, s[j]-s[i-1]);

分治法使时间复杂度更优

int maxum(int *a,int x,int y)//返回数组在[x,y)区间中最大连续和
{
int v,l,r,maxs;
if(y-x==1)return a[x];//只有一个元素，直接返回
int m=(x+y)/2;
int maxs=max(maxsum(a,x,m),maxsum(a,m,y));//分治第二步：递归求解
v=0;l=a[m-1];
for(int i=m-1;i>=x;i--)l=max(l,v+=a[i]);//分治第三步合并(1)：从分界点开始往左的最大连续和l
v=0;r=a[m];
for(int i=m;i<y;i++)r=max(r,v+=a[i]);//分支第三部合并(2):从分界点开始往右的最大连续和r
return max(maxs,l+r);//把子问题的解与l和r比较
}

用前面时间复杂度为 $O(n^{2})$ 的代码加以改进，在的到s后对数组进行维护，得到s的前i项最小，在后面的是s[j]-s[i-1]中只要找到最小的s[i-1]就ok了，所以只要直接减去维护后的s[i-1]就可以了。