问题
多项选择题
已知一个由正数组成的序列a1，a2，…，an，在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数，我们定义其子段之和为0。如果子段之和为正整数，那么就保留其为子段之和。请设计算法求出序列中的最大子段之和。
[要求]
写出算法的实现函数；
答案
参考答案：算法的实现过程如下：
int Maxsum(int n, int * a, int &besti, int &bestj){
/**本算法用于求出最大子段之和
*返回:最大子段和
*/
int max=0,i,j,tj,tmax,flag,sum;
for(i=A;i＜=n;i++){
flag=0;
sum=0;
tmax=*(a+i); //tmax暂时保存子段和
for(j=i;j＜=n;j++){
if(flag==0){ //判断是否都是负数
if(*(a+j) ＞0){
flag=A; //flag=A时，表示该子段的元素并不是全都是负数
tj=j-A;
}else{
tj=j;
tmax=0; //按照定义全负数之和为0
}
}
sum=sum+*(a+j);
if(sum＞tmax){ //记录下子段和
tmax=sum;
tj=j;
}
}
if(tmax＞=max){ //记录下更大的子段和
max=tmax;
besti=i;
bestj=tj;
}
}
return max;
}