我同学给我出了个难题,就是求一个数列的最大和连续子数列.
其定义为原数列中连续的数之和最大的数列.
如:
1 -3 4 5的最大子数列为:4,5,因为4+5最大.
3 4 -5 8 -4的最大子数列为:3,4,-5,8,因为3+4-5+8最大为10
4 3 -1 2的最大子数列为4,3,-1,2,因为4+3-1+2最大为8

其要求为:
1.第一行,用户输入n(数列个数);
2.第二行,输入数列各个数;
3.空一行
4.最大子数列和sum;
5.最大子数列;

如第一例为:
Input n:4
1 -3 4 5

sum=9
4,5

大家做做.希望以此提高自己编写程序的能力.

自己编了差不多一个小时,主要时间用于调试,因为题义不太了解. 如下是我的程序,仅供参考,如有问题,请与我联系.qq:283421560 还有就是哪位有更好的程序,算法,告诉我,谢谢了. #include<stdio.h> #include<conio.h> #define N 100 int a[N];

void main( ) { int n,i,j,k[N],l,max,sum[N][N],s[N],m;

printf("Input n:"); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("\n");

for(i=0;i<n;i++) { s[i]=0; for(j=0;j<n;j++) sum[i][j]=0; }

for(i=0;i<n;i++) { for(j=i;j<n;j++) { sum[i][j]=0; for(m=i;m<=j;m++) sum[i][j]+=a[m]; }

s[i]=sum[i][i]; k[i]=i; for(j=i+1;j<n;j++) if(sum[i][j]>s[i]) { s[i]=sum[i][j]; k[i]=j; } }

max=s[0]; l=0; for(i=1;i<n;i++) if(s[i]>max) { max=s[i]; l=i; } printf("sum=%d\n",max); for(i=l;i<=k[l];i++) printf("%d,",a[i]); getch( ); }

O(n^2) 比你的 O(n^3)好一些：） /* http://bbs.bc-cn.net/bbs/dispbbs.asp?boardID=5&ID=19147&page=2 最大和子序列 */

#include <stdio.h>

#define MAX_N 100

int main() { int num[MAX_N], sum[MAX_N]; int n, i, j, s; int bestBegin, bestEnd, bestSum; while(scanf("%d", &n) == 1 && n > 0) { for (i = 0; i < n; i++) scanf("%d", &num[i]); sum[0] = num[0]; for (i = 1; i < n; i++) sum[i] = sum[i-1] + num[i]; bestBegin = 0; bestEnd = 0; bestSum = num[0]; for (i = 0; i < n; i++) { for (j = i; j < n; j++) { s = i > 0? sum[j] - sum[i-1] : sum[j]; if (s > bestSum) { bestSum = s; bestBegin = i; bestEnd = j; } } } printf("%d\n%d", bestSum, num[bestBegin]); for (i = bestBegin+1; i <= bestEnd; i++) { printf(" %d", num[i]); } printf("\n"); } return 0; }

确实好.
s = i &gt; 0? sum[j] - sum[i-1] : sum[j];
这个语句什么意思啊?
if(i&gt;0)
 s=sum[j]-sum[i-1];
else
 s=sumj];
但是i除第一个之外总是大于0的啊?
是不是理解错了.

你没有理解错，只是我不想为了这个特例而把循环体单独拿出去写一遍。