- Time limit1000 ms
- Memory limit32768 kB
给定 K 个整数的序列 {N1, N2, ..., NK}, 其任意连续子序列可表示为 { Ni, Ni+1, ...,
Nj }, 其中 1 <= i <= j <= K. 最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列 { -2, 11, -4, 13, -5, -2 }, 其最大连续子序列为 { 11, -4, 13 }, 最大和
为 20.
在今年的数据结构考卷中, 要求编写程序得到最大和, 现在增加一个要求, 即还需要输出该
子序列的第一个和最后一个元素.
Input 测试输入包含若干测试用例, 每个测试用例占 2 行, 第 1 行给出正整数 K( <10000 ), 第 2 行给出 K 个整数, 中间用空格分隔. 当 K 为 0 时, 输入结束, 该用例不被处理.
Output 对每个测试用例, 在 1 行里输出最大和, 最大连续子序列的第一个和最后一个元
素, 中间用空格分隔. 如果最大连续子序列不唯一, 则输出序号 i 和 j 最小的那个 (如输入样例的第 2,3 组). 若所有 K 个元素都是负数, 则定义其最大和为 0, 输出整个序列的首尾元素.
- Sample Input
- 6
- -2 11 -4 13 -5 -2
- 10
- -10 1 2 3 4 -5 -23 3 7 -21
- 6
- 5 -8 3 2 5 0
- 1
- 10
- 3
- -1 -5 -2
- 3
- -1 0 -2
- 0
- Sample Output
- 20 11 13
- 10 1 4
- 10 3 5
- 10 10 10
- 0 -1 -2
- 0 0 0
- Huge input, scanf is recommended.
- Hint
- Hint
题解 可以说是动态规划, 也可以说是贪心啦, 每一次都累加, 只要累加起来的大于 0 就可以继续累加, 如果小于 0 了, 那就从下一个开始重新累加
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<sstream>
- #include<cmath>
- #include<cstdlib>
- #include<queue>
- #include<stack>
- using namespace std;
- #define PI 3.14159265358979323846264338327950
- int a[10004];
- #define INF 0x3f3f3f3f
- int main()
- {
- int n,i;
- while(scanf("%d",&n) && n)
- {
- int start,l,end,max=-INF,sum=0;
- for(i=0;i<n;i++)
- scanf("%d",&a[i]);
- int x=0;
- for(i=0;i<n;i++)
- {
- if(a[i]<0)
- x++;
- }
- if(x==n)
- printf("0 %d %d\n",a[0],a[n-1]);
- else
- {
- l=end=start=a[0];
- for(i=0;i<n;i++)
- {
- sum+=a[i];
- if(sum>max)
- {
- max=sum;
- start=l;
- end=a[i];
- }
- if(sum<=0)
- {
- sum=0;
- l=a[i+1];
- }
- }
- printf("%d %d %d\n", max, start, end);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2733409.html