连续子数组的最大和
发布日期: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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:调整数组顺序使奇数位于偶数前面
下一篇:链表中倒数第k个节点

发表评论

最新留言

表示我来过!
[***.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
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2019-04-21
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2019-04-21
计算机二级java技巧,计算机二级报java难考吗 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 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
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21