Question

给定一个整数序列，求出子段序列的最大和，也就是一段连续和元素的和，使其和最大，（如果

要详细的代码和一定的注释

Answer 1

#include <stdio.h>

int MaxSum(int *a,int n) {

int i,sum = 0,max = 0;

bool flag1 = false,flag2 = false;

for(i = 0;i < n;i++) {

if(a[i] > 0) flag1 = 1;

if(a[i] < 0) flag2 = 1;

}

if(flag1 && flag2) { // 序列中有正数，也有负数

for(i = 0;i < n;i++) {

if(a[i] < 0) {

if(max < sum) {

max = sum;

sum = 0;

}

}

else sum += a[i];

}

if(max < sum) max = sum;

}

else if(flag1 && !flag2) { // 全部为正

for(i = 0;i < n;i++) max += a[i];

}

else if(!flag1 && flag2) {

max = a[0];

for(i = 1;i < n;i++) {

if(a[i] > max) max = a[i];

}

}

else max = 0; // 全部为零

return max;

}

int main() {

int a[] = {31,-98,45,77,89,12,-92,88,80,120};

for(int i = 0;i < 10;i++) printf("%d ",a[i]);

printf("\nMAX = %d\n\n",MaxSum(a,10));

return 0;

}

Answer 2

上面的解答明显不是满足连续和最大的解：如：int a[] = {31,-98,45,77,89,12,-92,88,80,120};是你自己给的例子，那么按照你的算法得出的Max=288；那么45,77,89,12,-92,88,80,120的和是多少呢？显然大于288.(注意这几个数的和45,77,89,12,-92大于零)。下面我给出本人的代码：
#include<stdio.h>
int main(){
int max,sum,n,x;
while(scanf("%d",&n)!=EOF){
sum=0;
max=0;
while(n--){
scanf("%d",&x);
sum+=x;
if(sum>0){//sum大于0
if(sum>max){//sum大于max则sum赋值给max，否则继续加下一个数
max=sum;
}
}
else{//sum<0,置sum为0
sum=0;
}
}
printf("%d\n",max);
}
return 0;
}
如3 2 -7 6 5 -10 3，求其中连续数字最大的和的过程如下：
设两个变量，sum和max。
sum 从前往后做相加运算，如果sum为正，则max和sum比较，取较大的放入max；如果sum小于max，则继续向后加；如果sum小于0，则sum清除为0。对于上述数组，
1.
sum = 3
max = 3

sum = 5
max = 5

sum = -2
max =5 sum = 0

sum = 6
max = 6

sum = 11
max = 11

sum = 1
max = 11

sum = 4
max = 11

则最大数是11