女朋友在互联网公司做网站,电商网站设计公司力推亿企邦,视频网站做板块栏目,西安企业网站设计制作给定K个整数的序列{ N1, N2, ..., NK }#xff0c;其任意连续子序列可表示为{ Ni, Ni1, ..., Nj }#xff0c;其中 1 i j K。最大连续子序列是所有连续子序列中元素和最大的一个#xff0c; 例如给定序列{ -2, 11, -4, 13, -5, -2 }#xff0c;其最大连续子…给定K个整数的序列{ N1, N2, ..., NK }其任意连续子序列可表示为{ Ni, Ni1, ..., 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问题链接http://acm.hdu.edu.cn/showproblem.php?pid1231
问题分析动态规划问题
对于最原始的最大子序列和问题有一个函数模板大致思想如下 for(int i0;in;i)//n为输入序列的长度{if(cnt0)cnt 0;//cnt为记录当前序列和的变量else cntnum[i];//num数组为输入的序列if(cntmaxx)maxx cnt;//maxx用来保存最大序列和}AC
#includeiostream
#includestdio.h
using namespace std;
int main()
{int a[10005], n;while (cin nn){int u1;for (int i 0; i n; i) { scanf(%d, a[i]); if (a[i] 0 u)u 0; }if (u) { printf(0 %d %d\n, a[0], a[n - 1]); continue; }int sum -1000,s,e,maxn-1000,l,r;for (int i 0; i n; i){if (sum 0){sum a[i];l a[i];r a[i];}else sum a[i];if (sum maxn){maxn sum;s l;e a[i];}}if (maxn 0)printf(0 %d %d\n, s, e);else printf(%d %d %d\n, maxn, s, e);}
}
