连续子数组的最大和
发布日期:2021-06-20 02:50:12
浏览次数:5
分类:技术文章
本文共 407 字,大约阅读时间需要 1 分钟。
题目
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
思路
- 要求遍历一次就找到最大的数值。
- 时刻比较与当前和的值,如果当前数值小于1,证明对后面的和没有什么贡献,将其置0.
代码
class Solution { public: int maxSubArray(vector & nums) { int maxn = -0x3f3f3f3f, curSum = 0; for(auto d : nums){ curSum += d; maxn = max(maxn, curSum); if(curSum < 0) curSum = 0; } return maxn; }};
转载地址:https://blog.csdn.net/free1993/article/details/114876389 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年03月15日 17时30分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
冰点下载器手机版apk_冰点文库下载器
2019-04-21
python信号采集代码_13行代码实现:Python实时视频采集(附源码)
2019-04-21
h5引入json_纯js直接引入json文件
2019-04-21
python格式化字符串总结_Python字符串处理方法总结
2019-04-21
python中true什么意思_python中的bool是什么意思
2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么?
2019-04-21
c++ jna 数据类型_JNA 使用总结
2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表?
2019-04-21
java clone equals_(原)java中对象复制、==、equals
2019-04-21
计算机二级java技巧,计算机二级报java难考吗
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
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例
2019-04-21