01-复杂度2 Maximum Subsequence Sum (25 分)
发布日期:2022-02-10 08:11:11 浏览次数:14 分类:技术文章

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

在这里插入图片描述

题目大意:
找出数列的最大子列和,输出最大子列和,并输出最大子列和的头和尾
注意:
1.如果全为负数,则输出 0 数列第一个元素 数列最后一个元素
2.如果 全是0 和负数 则输出 0 0 0
一开始 对第一个元素的下标有点无从下手,后来想到在用在线求最大子列和时,每次更新最大子列和就能确定最后一个元素的下标,那么反过来用一个for循环 将 这个最大子列和一直减 直到他等于0,这个时候这个第一个下标就能找出来了。代码如下:
在这里插入图片描述
但是这样不能通过最大子列和前面 有0的情况:
如:
5
0 1 0 2 3
输出:6 1 3
可见从后面递减来求是有缺陷的 ,后来转念一想,我每次在线处理都是如果当前子列和为0就清空 再来求和,那么我可以直接设立一个临时变量,当thissum<0时,tempindex=i+1(这里很重要一定要tempindex 因为thissum会多次变化 只有更新最大子列和时这个index1=tempindex才是要求的);然后再在更新maxsum时,另index1=tempindex,就能完美的保存这两个数下标了!
代码如下:
在这里插入图片描述
这样就能AC啦!

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

上一篇:1886: 开门见“神”(数组两端轮流取值)
下一篇:自测-1 打印沙漏

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月18日 03时17分22秒

关于作者

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

推荐文章

python基础装饰器_Python基础 装饰器及练习 2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件 2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天 2019-04-21
springboot获取原生js请求_springboot跳转原生html 2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21
java导出类_java导出excel工具类 2019-04-21
java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21
mysql函数大全 pdf,MySQL函数大全 2019-04-21
php 常用文件系统函数,php 文件系统函数整理介绍 2019-04-21
android pm.java,java – AM / PM的Android DateFormat因设备而异 2019-04-21
oracle存储过程调用sql文件,oracle - 在SQL Developer中运行存储过程? 2019-04-21
oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21