1093：最大子序列

1093: 最大子序列
时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版]
题目描述
对于给出的K个整数的序列{ N1, N2, ..., NK }.，其连续的子序列定义为 { Ni, Ni+1, ..., Nj }，其中1 <= i <= j <= K. 最大子序列是其连续子序列中元素之和最大的子序列。例如：对于 { -2, 11, -4, 13, -5, -2 },  最大子序列为 { 11, -4, 13 }，最大和为20。编程找出其最大子序列。

输入
每个输入包含两行，第一行表示序列个数K，第二行为序列的K个元素，各元素间用空格分隔。

输出
最大子序列，如果存在具有相等最大和，则全部输出，每个序列一行。

样例输入
10
-10 1 2 3 4 -5 -23 3 7 -21
样例输出
1 2 3 4

3 7

这个题目，一开始结果只能输出一组数据，尝试记录多组结果失败了。

在论坛发帖提问，得到两个比较好的回答，一个直接在我的程序上进行了修改，思路比较清晰，就是双重循环，

另一个程序很简洁优美，不过我还没有完全理解到能自己打出来的程度orz

总之先搬上来。

首先是易于理解的版本

#include <iostream>
using namespace std;
const int N = 100;typedef struct START_AND_END
{int start;int end;
}startAndEnd;int main(){int k;int a[N];int i, j, m, n;startAndEnd sign[N];int signSize = 0;cin >> k;for (i = 0; i < k; i++)cin >> a[i];/*int start[10] = { 0 }, end[10] = { 0 };*/int start = 0, end = 0;int count = 0;int sum[N];memset(sum, 0, sizeof(sum));sum[0] = a[0];int max=0;for (i = 0; i < k; i++){//初始化，最大值为a[i]sum[i] = a[i];for (j = i + 1; j < k; j++){sum[i] += a[j]; //从a[i]开始逐个往后加，如果子序列的和大于当前最大的和，更新最大值，同时标记endif (sum[i]>max){max = sum[i];sign[signSize].start = i; sign[signSize].end = j;}}}for (i = 0; i < k; i++){//cout << i;//初始化，最大值为a[i]sum[i] = a[i];for (j = i + 1; j < k; j++){//cout << j;sum[i] += a[j]; //从a[i]开始逐个往后加，如果子序列的和大于当前最大的和，更新最大值，同时标记endif (sum[i] == max){for(m = 0; m < N; m++){if(sign[m].start != i){signSize++;sign[signSize].start = i;sign[signSize].end = j;for (n = sign[signSize].start; n <= sign[signSize].end; n++){cout << a[n] << " ";}cout << "\n";break;}}}}}system("pause");return 0;
}

然后是一位高手的版本

const int N=1000;
int a[N],s[N],t[N],ct,n,ans;int main(void)
{while(cin>>n && n){for(int i=0;i<n;i++) cin>>a[i];ans =-1e9;ct  =0;for(int i=0,pre=0,sum=0;i<n;i++){if((sum +=a[i]) <=0){pre=i+1;sum=0;continue;}if(sum<ans) continue;if(sum>ans) ct =0, ans=sum;s[ct]=pre, t[ct++] =i;}for(int i=0;i<ct;i++) {cout<<a[s[i]];for(int j=s[i]+1;j<=t[i];j++) cout<<' '<<a[j];cout<<endl;}}return 0;
}

暑假作业算是折腾完一遍了，不过发文章记录是中途开始的，之后几天也会把之前的题目再做几遍，把部分题目整理一下……哎，实验报告还没写，开学小学期还有编程能力测试，我的心好痛TVT

努力吧，被C++逼婚只能硬着头皮上啊啊啊

多思考，多编程

Errors == more coding^2~