动态规划---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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:二叉树
下一篇:HDU 动态规划(46道题目)倾情奉献~ 【只提供思路与状态转移方程】

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月17日 10时01分04秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java build path jre_java-如何在安装了jre 7后为Jre 6设置路径? 2019-04-21
java上传下载源码_javaweb简单实现文件上传与下载源代码 2019-04-21
java socket udp 广播_1.Java 的屏幕广播(基于UDP),2.多线程下载器 2019-04-21
java控制热敏打印机的例子.rar_stm32控制热敏打印机 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2019-04-21
java滚动字幕实训报告_Java实习报告 (7000字).doc 2019-04-21
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2019-04-21
计算机二级java技巧,计算机二级报java难考吗 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 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
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
c语言枪图形,6个变态的C语言Hello World程序[转载] 2019-04-21
郑州大学c语言课程设计2000行,C语言课程设计大作业(1).pptx 2019-04-21
Android5.1自定义闹钟铃声,Android 设置来电铃声、通知铃声、闹钟铃声中的坑 2019-04-21
android 程序更换字体,Android修改自己程序字体的方法详解 2019-04-21
c语言4x4矩形列互换,线反转法4x4键盘C语言程序问题.急... 2019-04-21
android服务开启线程,android之service与intentService的不同 2019-04-21