hdu1231 最大连续子序列--DP
发布日期:2021-10-03 20:31:49 浏览次数:12 分类:技术文章

本文共 1751 字,大约阅读时间需要 5 分钟。

原题链接:

一:原题内容

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   
Hint
Hint
Huge input, scanf is recommended.

二:分析理解

直接上代码吧。。。。

三:AC代码

#include
#include
#include
using namespace std;int a[10005];int main(){ int N; while (scanf("%d", &N) && N) { for (int i = 0; i < N; i++) scanf("%d", &a[i]); int max = a[0]; int cnt = a[0]; int left = a[0]; int right = a[0]; int flag = a[0]; for (int i = 1; i < N; i++) { if (cnt < 0) { flag = a[i]; cnt = a[i]; } else cnt += a[i]; if (cnt > max) { left = flag; right = a[i]; max = cnt; } } if (max < 0) { printf("%d %d %d\n", 0, a[0], a[N - 1]); continue; } printf("%d %d %d\n", max, left, right); } return 0;}

#include
#include
using namespace std;int dp[100]; //表示以i为尾的最大连续子序列int N;int sum;int main(){ while (cin >> N) { for (int i = 0; i < N; i++) cin >> dp[i]; if (dp[0] < 0) //初始化 dp[0] = 0; int sum = dp[0]; for (int i = 1; i < N; i++) { if (dp[i] + dp[i - 1] >= 0) { dp[i] += dp[i - 1]; if (dp[i] > sum) sum = dp[i]; } else dp[i] = 0; } cout << sum << endl; }}

转载地址:https://blog.csdn.net/LaoJiu_/article/details/50933360 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1003 Max Sum--DP
下一篇:hdu3068 最长回文--Manacher算法

发表评论

最新留言

很好
[***.229.124.182]2024年03月19日 02时57分41秒

关于作者

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

推荐文章

java 符号 t_java – 运算符”不能应用于’T’,’T’表示有界泛型类型 2019-04-21
用matlab写出信源熵,计算离散信源的熵matlab实现 2019-04-21
php表单yii2,Yii2创建表单(ActiveForm)方法详解 2019-04-21
php 程序授权机制,授权认证详细说明 2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令? 2019-04-21
IP/tzgm.php,LianjiaSpider/在售数量.ipynb at master · BerSerK/LianjiaSpider · GitHub 2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件 2019-04-21
linux查看系统所有变量,Linux系统各指标命令 2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢? 2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21