PAT (Advanced Level) 1007 Maximum Subsequence Sum (25 分)
发布日期:2021-06-29 12:22:26
浏览次数:2
分类:技术文章
本文共 938 字,大约阅读时间需要 3 分钟。
题目概述:
给定数组,求和最大的子序列,输出其最大和以及子序列首尾元素。若全为负数,则输出和为0,以及整个数组的首尾元素。分析:
这是一道动态规划,但可以不用dp 1.用tempsum表示当前记录的和,若大于sum,则存下目前的最大值以及首尾序号 2.若tempsum < 0,说明这里的记录可以舍弃(因为只会起负作用),并把tempsum置为0,同时tempindex设为i + 1#includeusing namespace std;int main(){ int k; cin >> k; int sum = -1, l = 0, r = k - 1, tempsum = 0, tempindex = 0; vector vt(k); for(int i = 0; i < k; i++) { cin >> vt[i]; tempsum += vt[i]; if(tempsum > sum) { sum = tempsum; l = tempindex; r = i; } else if(tempsum < 0) { tempindex = i + 1; tempsum = 0; } } if(sum == -1) { sum = 0; cout << sum << " " << vt[0] << " " << vt[k-1] << endl; return 0; } cout << sum << " " << vt[l] << " " << vt[r] << endl; return 0;}
总结:
1.注意审题,这里是输出首尾元素,而不是序号!!! 2.sum的初始值要设置为-1,这样可以对全部为负数的情况进行识别。转载地址:https://bridge-killer.blog.csdn.net/article/details/115432899 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月15日 20时16分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
使用urdf_tutorial快速可视化urdf文件
2019-04-29
SQl 数据完整性(随堂博客)
2019-04-29
左连接、右连接、内连接
2019-04-29
MySQL DQL语句基础(随堂博客)
2019-04-29
MySQL基础练习
2019-04-29
利用MySQL进行数据复杂查询(1)
2019-04-29
利用MySQL进行数据复杂查询(2)
2019-04-29
MySQL 表与表之间的关系
2019-04-29
MySQL常见错误总结
2019-04-29
pymysql 的基础应用
2019-04-29
Python 管理程序改进——连接MYSQL
2019-04-29
Python 爬虫-豆瓣影星图片下载
2019-04-29
网页端数据库操作界面—主题函数文件
2019-04-29
网页端数据库操作界面-Html页面(1)
2019-04-29
Python爬虫 百度热搜热点
2019-04-29
excel的常用函数(二)
2019-04-29
excel文本函数
2019-04-29
电商大战二十年
2019-04-29
编程程软件测试思维方式:如何科学制定测试计划
2019-04-29