3616 - 最大和
现给定一串数N，求出连续的数相加的最大值，例如：1 6 9 -5 4，连续数的最大和就是1+6+9=16；6 -3 4 0
-1，连续数的最大和是6+（-3）+4=7；
题目输入
测试包含多组测试数据,每组测试数据包含两行，
第一行输入一个整数N
1<=N<=100
接下来一行含有N个数，保证每个数取值范围是（-100000，+100000），两个数中间用空格隔开
题目输出
对于每组测试数据输出连续数的最大和
输入/输出样例
题目输入
5 1 6 9 -5 4 5 6 -3 4 0 -1
题目输出
16 7
提示
出题人：杨浩
C语言解答
#include <stdio.h> int main() { int N; int a[100],i,j,k; int thisSum=0,maxSum=0; while(scanf("%d",&N)!=EOF&&N>=1&&N<=100) { for(i=0;i<N;i++) { scanf("%d",&a[i]); } maxSum=a[0]; for ( i = 0; i<N; i++ ) { for (j = 1; j<N; j++ ) { thisSum = 0; for ( k = i; k <= j; k++ ) { thisSum+= a[k]; } if ( thisSum > maxSum ) { maxSum=thisSum; } } } printf("%d\n",maxSum); } return 0; }
C++解答
#include <bits/stdc++.h> using namespace std; int main() { int n; while(~scanf("%d",&n)){ int a[105]; for (int i=0;i<n;i++){ scanf("%d",&a[i]); } int d[105]; memset(d,0,sizeof(d)); if (a[0]>=0) d[0]=a[0]; int maxx=d[0]; for (int i=1;i<n;i++){ if (d[i-1]+a[i]>0) d[i]=d[i-1]+a[i]; maxx=max(maxx,d[i]); } printf("%d\n",maxx); } return 0; }
提示
出题人：杨浩