经典指数          
原因
563
浏览数
0
收藏数
 

最大连续子数列和 给出一个数列(元素个数不多于100),数列元素均为负整数、0、正整数。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多,并输出这个最大和以及该连续子数列在整个数列中的位置。 例如数列为4  -5  3  2  4时,输出“和为9,子数列起始位置为2,结束位置为4”;再比如数列为1  2  3  -5  0  7  8时,输出“和为16,子数列起始位置为0,结束位置为6”。 键盘输入:为两行,第一行为数列元素个数,第二列依次输入各个元素。 7 1 2 3 -5 0 7 8 屏幕输出: 和为16,子数列起始位置为0,结束位置为6 #include int seek(int a[100],int n,int *p1,int *p2) { int i1,i2,i3,t1=0,t2=n-1,sum=0,max; for (i1=0;i1=i1;i2--) { for (i3=0;i3<=i2;i3++)    sum=sum+a[i3]; if (i1==0&&i2==n-1) max=sum; else  { if (sum>max) { t1=i1; t2=i2; max=sum; } else if (sum==max) { if (i2-i1>t2-t1) { t1=i1; t2=i2; } } } sum=0; } } *p1=t1; *p2=t2; return (max); } void main() { int a[100],t1,t2,n,i,max; int *p1,*p2; scanf("%d",&n); fflush(stdin); for (i=0;i

     举报   纠错  
 
切换
1 个答案
O(n) int max_sub_sum(int a[]; unsigned int n) { int this_sum=0,max_sum=0,best_i=-1,best_j=-1; for(int i =0,j=0; j < n; j++){ this_sum += a[j]; if(this_sum > max_sum) { max_sum = this_sum; best_i = i; best_j = j; } else if(this_sum == max_sum && best_j - best_i < j - i) { best_i=i; best_j=j; } if(this_sum < 0) { i = j + 1; this_sum = 0; } } return max_sum; }
 
切换
撰写答案
扫描后移动端查看本题