当前位置: 首页 > news >正文

最大连续子数组

最大连续子数组(Maximum Subarray)问题是一个经典的算法问题,其目标是在给定的整数数组中找到一个连续的子数组,使得该子数组的元素之和最大。这个问题有多种解决方法,其中包括暴力解法、分治法和动态规划等。

下面是一个讲解最大连续子数组问题的常见解决方法:

  1. 暴力解法: 暴力解法是最简单的方法,它通过两层嵌套循环遍历所有可能的子数组,计算它们的和,并找到和最大的子数组。这个方法的时间复杂度是O(n^2),其中n是数组的长度。尽管它不是最高效的方法,但它是一个朴素而容易理解的解决方案。

  2. 动态规划: 动态规划是解决最大连续子数组问题的高效方法之一。在这种方法中,我们维护一个动态规划数组dp,其中dp[i]表示以第i个元素结尾的最大子数组和。动态规划的关键是通过递推关系来计算dp[i],这个关系通常是 dp[i] = max(dp[i-1] + nums[i], nums[i])。最终,最大子数组和就是dp数组中的最大值。这个方法的时间复杂度是O(n),其中n是数组的长度。

  3. 分治法: 分治法是另一种解决最大连续子数组问题的方法。它将数组分成三个部分:左子数组、右子数组和跨越中间的子数组。然后,递归地求解左子数组和右子数组的最大子数组和,以及跨越中间的最大子数组和。最后,将这三者中的最大值作为最终的结果。这个方法的时间复杂度是O(n*log(n)),其中n是数组的长度。

  4. Kadane算法: Kadane算法是一种高效的动态规划方法,用于解决最大连续子数组问题。它维护两个变量,cur表示当前子数组的和,maxv表示最大子数组和。在遍历数组的过程中,它不断更新curmaxv,并且当cur小于0时,将cur重置为0。最终,maxv就是最大子数组和。这个方法的时间复杂度是O(n),其中n是数组的长度。

我们来看看代码
 

int fun04(int* p, int left, int right);
void fun()
{int i=0, j=0, k=0;int len;int maxv;int v[] = { 1,-3,6,8,0,-7,8 };len = 7; maxv = v[0];for (int i = 0; i < len; i++){for (j = i; j < len; j++){if (j == i){maxv = max(maxv, v[j]);}else {v[i] += v[j];maxv = max(maxv, v[i]);}}}cout << maxv << endl;
}
void fun01()
{int v[] = { 1,-3,6,8,0,-7,8 };int dp[7];dp[0] = v[0];int maxv = dp[0];for (int i = 1; i < 7; i++){dp[i] = max(dp[i - 1] + v[i], v[i]);maxv = max(maxv, dp[i]);}cout << maxv << endl;
}void fun02() {int v[] = { -2,-1 };int maxv = v[0];int cur = 0; for (int i = 0; i < 2; i++) {cur += v[i];maxv = max(maxv, cur);if (cur >= 0) {maxv = max(maxv, cur);}else {cur = 0;}}cout << maxv << endl;
}void fun03() {int v[] = { 1,-3,6,8,0,-7,8 };cout << fun04(v, 0, 6);
}
int fun04(int* p, int left, int right) {if (left == right) {return p[left];}int mid = (left + right) >> 1;int maxleft = fun04(p, left, mid);int maxright = fun04(p, mid + 1, right);int tmpleft = p[mid - 1];int tmp = tmpleft;for (int i = mid - 2; i >= 0; i--) {tmp += p[i];tmpleft = max(tmp, tmpleft);}int tmpright = p[mid + 1];tmp = tmpright;for (int i = mid + 2; i < right; i++){tmp += p[i];tmpright = max(tmp, tmpright);}int midmax = p[mid] + (tmpleft > 0 ? tmpleft : 0) + (tmpright > 0 ? tmpright : 0);return max(maxleft, maxright > midmax ? maxright : midmax);
}

上面的代码演示了几种不同的方法来找到数组中的最大子数组和(最大子序列和问题),并进行了简要的分析。

  1. fun() 方法使用了嵌套的两个 for 循环来遍历所有可能的子数组和,同时维护最大值。这是一种朴素的暴力解法,时间复杂度为O(n^2),其中n是数组的长度。

  2. fun01() 方法使用了动态规划的思想,维护一个dp数组,其中dp[i]表示以第i个元素结尾的最大子数组和。在遍历数组的过程中,根据前一个元素的最大子数组和来计算当前元素的最大子数组和,从而避免了重复计算。这种方法的时间复杂度为O(n),其中n是数组的长度。

  3. fun02() 方法是一种更简单的方法,它遍历一次数组,同时维护当前子数组的和cur和最大子数组和maxv。当cur小于0时,表示当前子数组和不再对最大子数组和有贡献,需要将cur重置为0。这种方法也是O(n)时间复杂度。

  4. fun03() 方法是一个递归的分治方法,其中 fun04() 函数采用分治思想来寻找最大子数组和。它将数组分为左右两部分,然后分别计算左部分、右部分以及跨越中间的最大子数组和,然后取三者中的最大值作为最终的结果。这个方法的时间复杂度也是O(n*log(n)),因为它每次将数组分成两半,需要进行递归处理。

总的来说,动态规划方法(fun01()fun02())是解决最大子数组和问题的较优解,具有O(n)的时间复杂度,而分治方法(fun03())也是一个有效的算法,但在实际情况中可能不如动态规划方法高效。朴素的暴力解法(fun())具有O(n^2)的时间复杂度,不适用于大规模数据。选择合适的算法取决于实际问题和性能要求。

相关文章:

最大连续子数组

最大连续子数组&#xff08;Maximum Subarray&#xff09;问题是一个经典的算法问题&#xff0c;其目标是在给定的整数数组中找到一个连续的子数组&#xff0c;使得该子数组的元素之和最大。这个问题有多种解决方法&#xff0c;其中包括暴力解法、分治法和动态规划等。 下面是…...

【FastCAE源码阅读5】使用VTK实现鼠标拾取对象并高亮

鼠标拾取对象是很多软件的基本功能。FastCAE的拾取比较简单&#xff0c;是通过VTK实现的。 对几何而言&#xff0c;拾取类型切换在工具栏上&#xff0c;单击后再来单击视图区对象进行拾取&#xff0c;拾取后的对象会高亮显示。效果如下图&#xff1a; 一、拾取对象 拾取对象…...

【全志H616 使用标准库 完成自制串口库(分文件实现) orangepi zero2(开源)】.md updata: 23/11/07

文章目录 H616 把玩注意&#xff1a;Linux内核版本5.16 及以上&#xff0c;需手动配置i2c-3 uart5驱动配置示例 分文件编译时需将每个文件一同编译 &#xff08;空格隔开&#xff09;例&#xff1a; ggc a.c b.c b.h -lpthread -lxxx..; 常用命令查看驱动文件查看内核检测信息/…...

小白学爬虫:手机app分享商品短连接获取淘宝商品链接接口|淘宝淘口令接口|淘宝真实商品链接接口|淘宝商品详情接口

通过手机APP分享的商品短链接&#xff0c;我们可以调用相应的接口来获取淘口令真实URL&#xff0c;进而获取到PC端的商品链接及商品ID。具体步骤如下&#xff1a; 1、通过手机APP分享至PC端的短链接&#xff0c;调用“item_password”接口。 2、该接口将返回淘口令真实URL。 3…...

python 应用之 request 请求调用

场景&#xff1a; 验证一个第三方接口 目录 一、应用实例 1、预准备工作 1&#xff09;、引用包 2&#xff09;、生成随机串 3&#xff09;、获得当前时间戳 4&#xff09;、HASH 5&#xff09;、header处理 6&#xff09;、请求处理 2、requests请求 1&#xff09…...

BeanUtils.copyProperties浅拷贝的坑你得知道?

今天想写一篇文章&#xff0c;主要关于深拷贝和浅拷贝相关的&#xff0c;主要是最近写代码的时候遇到一个BUG&#xff0c;刚好涉及到浅拷贝导致的问题。 问题背景 现在有一个需要是需要修改门店信息&#xff0c;门店也区分父门店和子门店&#xff0c;父门店被编辑更新是需要通过…...

ubuntu安装rabbitMQ 并 开启记录消息的日志

apt-get update apt-get install rabbitmq-server rabbitmqctl add_user root password // 设置用户名密码 rabbitmqctl set_user_tags root administrator // 设置为管理员身份 rabbitmqctl set_permissions -p / root ".*" ".*" ".*" //为…...

思维模型 首因效应

本系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。先入为主&#xff0c;一见钟情。 1 首因效应的应用 1.1 面试中的首因效应 小李是一名应届毕业生&#xff0c;他准备参加一家知名互联网公司的面试。在面试前&#xff0c;他做了充分的准备…...

Redis极速上手开发手册【Redis全面复习】

文章目录 什么是RedisRedis的特点Redis的应用场景Redis安装部署Redis基础命令Redis多数据库特性Redis数据类型Redis数据类型之stringRedis数据类型之hashRedis数据类型之listRedis数据类型之setRedis数据类型之sorted set案例&#xff1a;存储高一班的学员信息 Redis封装工具类…...

[动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子

[动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子 文章目录 [动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结 LCR 091. 粉刷房子 题目解析 (1) 一排房子&#xff0c;共有n个 (2) 染…...

【VSS版本控制工具】

VSS版本控制工具 1 安装 VSS2 服务器端配置3 新建用户4 客户端配置Vss2005Vs20055 客户端详细操作 1 安装 VSS 第一步&#xff1a;将VisualSourceSafe2005安装包解压。 第二步&#xff1a;找到setup.exe双击运行。 第三步&#xff1a;在弹出的界面复选框中选中Iaccepttheterms…...

数据持久化技术(Python)的使用

传统数据库连接方式&#xff1a;mysql&#xff08;PyMySQL&#xff09;ORM 模型&#xff1a;SQLAlchemy MyBatis、 Hibernate PyMySQL 安装&#xff1a; pip install pymysql简单使用 利用 pymysql.connect 建立数据库连接并执行 SQL 命令&#xff08;需要提前搭建好数据库…...

第23章(上)_索引原理之索引与约束

文章目录 索引索引分类主键选择索引的代价 约束外键约束约束与索引的区别 索引使用场景不要使用索引的场景总结 索引 索引的概念&#xff1a;索引是一种有序的存储结构。索引按照单个或多个列的值进行排序。 索引的目的&#xff1a;提升搜索效率。 索引分类 按照数据结构分为…...

金蝶云星空BOS设计器中基础资料字段属性“过滤”设置获取当前界面的基础资料值作为查询条件

文章目录 金蝶云星空BOS设计器中基础资料字段属性“过滤”设置获取当前界面的基础资料值作为查询条件背景说明业务需求格式BOS配置 金蝶云星空BOS设计器中基础资料字段属性“过滤”设置获取当前界面的基础资料值作为查询条件 背景说明 序列号档案是基础资料&#xff0c;资料里…...

OFDM深入学习及MATLAB仿真

文章目录 前言一、OFDM 基本原理及概念1、OFDM 简介2、子载波3、符号4、子载波间隔与符号长度之间的关系 二、涉及的技术1、保护间隔2、交织3、信道编码4、扩频5、导频6、RF&#xff08;射频&#xff09;调制7、信道估计 三、变量间的关系四、IEEE 802.11a WLAN PHY 层标准五、…...

软件测试简历原来是写了这些才让面试官已读不回

前言&#xff1a; 马上就到了面试跳槽涨薪好时候了&#xff0c;最近看很多的小伙伴已经开始投简历了&#xff0c;一天投了几十次几百次&#xff0c;面试官已读不会&#xff0c;面试的机会都没有更别说后面的事情的&#xff0c;这是为什么呢&#xff1f; 很大一部分的原因是的…...

ESP32网络开发实例-Web服务器RGB LED调光

Web服务器RGB LED调光 文章目录 Web服务器RGB LED调光1、RGB LED介绍3、软件准备4、硬件准备4、代码实现在本文中,我们将创建一个 RGB LED 控制器网络服务器。 Web 服务器将显示用于设置 RGB LED 颜色的色谱。 颜色将主要分为三种:红色、绿色和蓝色。 用户将从光谱中选择一种…...

C# TCP Server服务端多线程监听RFID读卡器客户端上传的读卡数据

本示例使用设备介绍&#xff1a;液显WIFI无线网络HTTP协议RFID云读卡器可编程实时可控开关TTS语-淘宝网 (taobao.com) using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using Sy…...

【electron】【附排查清单】记录一次逆向过程中,fetch无法请求http的疑难杂症(net::ERR_BLOCKED_BY_CLIENT)

▒ 目录 ▒ &#x1f6eb; 导读需求开发环境 1️⃣ Adblock等插件拦截2️⃣ 【失败】Content-Security-Policy启动服务器json-serverhtml中的meta字段 3️⃣ 【失败】https vs httpwebPreferences & allowRunningInsecureContent disable-features 4️⃣ 【失败】检测fetch…...

【JS】scrollTop+scrollHeight+clientTop+clientHeight+offsetTop+offsetHeight

scrollTop、scrollHeight、clientTop、clientHeight、offsetTop以及offsetHeight 1. scrollTop 与 scrollHeight 1.1 scrollTop scrollTop 是这六个属性中唯一一个可写的属性。 Element.scrollTop 属性可以获取或设置一个元素的内容垂直滚动的像素数。 一个元素的 scrollT…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...