PAT (Advanced Level) 1007 Maximum Subsequence Sum (25 分)
发布日期:2021-06-29 12:22:26 浏览次数:3 分类:技术文章

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

题目概述:

给定数组,求和最大的子序列,输出其最大和以及子序列首尾元素。若全为负数,则输出和为0,以及整个数组的首尾元素。

分析:

这是一道动态规划,但可以不用dp
1.用tempsum表示当前记录的和,若大于sum,则存下目前的最大值以及首尾序号
2.若tempsum < 0,说明这里的记录可以舍弃(因为只会起负作用),并把tempsum置为0,同时tempindex设为i + 1

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

上一篇:PAT (Advanced Level) 1011 World Cup Betting (20 分)
下一篇:PAT (Advanced Level) 1010 Radix (25 分)

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年04月28日 17时39分56秒

关于作者

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

推荐文章

JAVA 线程同步机制 synchronized 2019-04-29
MySQL 安装教程(无脑版) 2019-04-29
IDEA 怎么删除一个Module 2019-04-29
走进数据科学:最好是通过比网课更好的方法 2019-04-29
AI革命第一步:最容易被忽略但必不可少的物联网 2019-04-29
2020年开发运维工具清单:选择开发运维工具堆栈吧 2019-04-29
效率提升法则:高效人士不会去做的4件事 2019-04-29
8.PostgreSQL约束 2019-04-29
【技术分享】使用AES加密技术保障数据安全 2019-04-29
【应用实例】布线多?成本高?不可靠?泽耀方案没烦恼! 2019-04-29
数据可视化工具:Matplotlib绘图 2019-04-29
用Python写个超级小恐龙跑酷游戏,上班摸鱼我能玩一天 2019-04-29
闺蜜看我用Python画了一幅樱花图,吵着要我给他介绍程序员小哥哥 2019-04-29
【Python爬虫实战】知乎热榜数据采集,上班工作摸鱼两不误,知乎热门信息一网打尽 2019-04-29
自从我学会了数据挖掘Matplotlib、Numpy、Pandas、Ta-Lib等一系列库,我把领导开除了 2019-04-29
Python抓取哔哩哔哩up主信息:只要爬虫学的好,牢饭吃的早 2019-04-29
有个码龄5年的程序员跟我说:“他连wifi从来不用密码” 2019-04-29
领导让我整理上个季度的销售额,幸好我会Python数据分析,你猜我几点下班 2019-04-29
【Python爬虫实战】为何如此痴迷Python?还不是因为爱看小姐姐图 2019-04-29
零基础自学Python,你也可以实现经济独立! 2019-04-29