动态规划---hdu1231---最大连续子序列
代码实现:
发布日期:2022-02-02 02:58:07
浏览次数:19
分类:技术文章
本文共 1121 字,大约阅读时间需要 3 分钟。
Problem Description
给定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 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20
Sample Output
20 11 1310 1 410 3 510 10 100 -1 -20 0 0
#include#include using namespace std;#define MAX 10007int main(){ int dp[ MAX ] ; int n ; while( cin>>n ) { if(n==0)break; int sum = 0 ; int temp= 0; int begin; int end; int Maxnum=-99999; for(int i = 0 ; i < n ; i++ ) { cin>>dp[i]; sum += dp[ i ] ; if( sum < 0 ) { temp= i + 1 ; sum=0; } else { if( Maxnum < sum ) { Maxnum = sum ; begin = temp; end=i; } } } if( Maxnum < 0 ) { cout<<"0 "< <<" "< <
转载地址:https://blog.csdn.net/u010368749/article/details/18980763 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年03月17日 10时01分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java上传下载源码_javaweb简单实现文件上传与下载源代码
2019-04-21
java控制热敏打印机的例子.rar_stm32控制热敏打印机
2019-04-21
java clone equals_(原)java中对象复制、==、equals
2019-04-21
java滚动字幕实训报告_Java实习报告 (7000字).doc
2019-04-21
计算机二级java技巧,计算机二级报java难考吗
2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc
2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点
2019-04-21
linux php mkdir失败,linux – mkdir错误:参数无效
2019-04-21
config.php渗透,phpMyAdmin 渗透利用总结
2019-04-21
c语言枪图形,6个变态的C语言Hello World程序[转载]
2019-04-21
郑州大学c语言课程设计2000行,C语言课程设计大作业(1).pptx
2019-04-21
android 程序更换字体,Android修改自己程序字体的方法详解
2019-04-21
c语言4x4矩形列互换,线反转法4x4键盘C语言程序问题.急...
2019-04-21