Leetcode 最大子数组和

在这里插入图片描述

使用“Kadane’s Algorithm”来解决。

Kadane’s Algorithm 在每个步骤中都保持着一个局部最优解,即以当前元素为结尾的最大子数组和(也就是局部最优解),并通过比较这些局部最优解和当前的全局最优解来找到最终的全局最优解

Kadane’s Algorithm的核心思想是:在遍历数组的过程中,动态地计算出以每个元素结尾的最大子数组和,并用一个变量来记录出现过的最大值。简单来说,它帮我们找到了一种巧妙的方式,在一次遍历中找到最大子数组的和。

通俗解释:

假设你有一个数组,比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4],你想找出这个数组中和最大的子数组。Kadane’s Algorithm通过以下步骤来完成这个任务:

  1. 从左到右遍历数组:你会逐个看数组中的每个数字。
  2. 累积当前的和:对于每个数字,你有两种选择:
    • 要么继续把它加到之前的子数组和里,扩展现有的子数组。
    • 要么丢弃之前的子数组,从这个数字重新开始一个新的子数组。
  3. 更新最大和:每当你计算出一个新的子数组和时,记录下目前为止遇到的最大值。

具体的步骤如下:

  • 假设一开始你的数组是 [-2, 1, -3, 4, -1, 2, 1, -5, 4],我们先从第一个数字开始。

  • 第一个数字是 -2,这就是目前为止最大的子数组和,所以暂时记录为最大值。

  • 接着看下一个数字 1。你现在有两个选择:

    1. 继续加:-2 + 1 = -1,即把1加到前面的子数组([-2])上。
    2. 重新开始:直接从1开始,子数组就变成了[1]

    很显然,1-1大,所以你选择从1重新开始一个子数组,并更新最大和为1

  • 再看下一个数字 -3,你又有两个选择:

    1. 继续加:1 + (-3) = -2
    2. 重新开始:从-3开始,子数组变成[-3]

    你会选择继续加,但最大和仍然保持不变为1

  • 继续这个过程,直到遍历完整个数组,每次你都比较是继续累加还是重新开始子数组,并始终记录出现过的最大子数组和。

最终,在这个例子里,你会发现最大子数组是 [4, -1, 2, 1],它的和是 6

核心思想总结:

  • Kadane’s Algorithm用一种局部最优解逐步构建出全局最优解。通过在每个位置上选择是继续累加还是重新开始子数组,你能够高效地找到整个数组的最大子数组和。
  • 每次你只关心当前元素,以及前面累加的结果,这使得算法可以在**O(n)**的时间内完成问题的求解。
class Solution {
public:int maxSubArray(vector<int>& nums) {//首先利用第1个元素分别初始化局部最优解和全局最优解int current_sum = nums[0];int max_sum = nums[0];for(int i = 1; i < nums.size(); ++i) {//首先更新当前局部最优解, 对当前元素,无非2种选择:1.作为新的子数组起点,2.作为当前子数组的末尾//我们对比这两种情况的子数组和,将最大值作为局部最优解。//这行代码很巧妙,不仅更新了局部最优解,也可以设置新的子数组起点current_sum = max(nums[i], current_sum + nums[i]);//更新完局部最优解之后,紧接着和全局最优解进行对比,更新全局最优解max_sum = max(current_sum, max_sum);}return max_sum;}
};

是的,Kadane’s Algorithm**属于动态规划(Dynamic Programming,DP)**的一种具体实现。

这行代码很巧妙,不仅更新了局部最优解,也可以设置新的子数组起点

current_sum = max(nums[i], current_sum + nums[i]);

这行代码确实是Kadane’s Algorithm中最巧妙的地方,关键在于它同时做了两件事:

  1. 更新局部最优解current_sum = max(nums[i], current_sum + nums[i]);的核心在于它选择了当前子数组的最优策略。它计算了两种可能的情况:

    • nums[i]:直接将当前元素作为新的子数组的起点,丢弃之前的累积和。
    • current_sum + nums[i]:将当前元素加到之前已经计算出来的子数组和中,继续扩展当前子数组。

    通过比较这两种情况,算法能在每个元素上做出最优决策,即决定当前子数组是否应该继续累积,还是应该重新开始。

  2. 自动设定新子数组起点:当nums[i] > current_sum + nums[i]时,这意味着累加前面的子数组和反而让和变小了,因此此时就选择从nums[i]重新开始一个新的子数组。也就是说,当前元素本身就大于累积的和时,它就自然成为新的子数组的起点。这样就无需显式地去标记子数组的起点,算法通过比较自动决定何时重置。

例子解释:

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例,我们逐步解释这行代码的行为:

  • 开始时:current_sum = -2max_sum = -2
  • 遍历到 1 时:current_sum = max(1, -2 + 1) = 1,此时直接从1重新开始,max_sum 更新为 1
  • 遍历到 -3 时:current_sum = max(-3, 1 - 3) = -2,继续累加,但max_sum保持不变。
  • 遍历到 4 时:current_sum = max(4, -2 + 4) = 4,重新开始一个新的子数组,max_sum 更新为 4

通过这种方式,每次都能判断是扩展子数组还是从当前元素重新开始,并确保每一步都在寻找最优解。

巧妙之处总结:

  • 简洁高效:通过一个简单的 max 比较,Kadane’s Algorithm不仅做到了局部最优解的更新,还自动完成了子数组的起点设定。相比于需要显式地处理每个子数组的起点和终点的其他算法,Kadane’s Algorithm更加简洁、优雅。
  • 避免冗余操作:无需存储额外的信息(如子数组的起点或终点),减少了空间开销,同时保持了O(n)的时间复杂度。

这就是为什么Kadane’s Algorithm被认为是一个非常经典且高效的解决最大子数组和问题的算法。

为什么Kadane’s Algorithm是动态规划?

  1. 重叠子问题:动态规划的核心思想之一是通过解决子问题来解决更大的问题。在Kadane’s Algorithm中,每个子数组和的最大值都依赖于前一个子数组的解。也就是说,当前位置的最优解依赖于前一个位置的最优解,这是“重叠子问题”的特性。

    • 例如,在当前位置i,我们只需要知道位置i-1处的最大子数组和,就能决定是否要把当前元素nums[i]加入到前面的子数组中,还是从当前元素重新开始。
  2. 最优子结构:动态规划要求问题具有最优子结构,即全局问题的最优解可以由子问题的最优解构造得到。在Kadane’s Algorithm中,整个数组的最大子数组和可以通过一系列局部最大子数组和的比较来得到。

    • Kadane’s Algorithm在每个步骤中都保持着一个局部最优解,即以当前元素为结尾的最大子数组和,并通过比较这些局部最优解来找到最终的全局最优解。

Kadane’s Algorithm的动态规划状态转移方程

动态规划常常有一个状态转移方程,用来更新每个子问题的最优解。Kadane’s Algorithm的状态转移方程可以表述为:

  • current_sum = max(nums[i], current_sum + nums[i])

这意味着:

  • 对于当前的元素nums[i],我们有两个选择:

    1. 把它加到前面的子数组上(current_sum + nums[i])。
    2. 或者,从当前元素开始一个新的子数组(nums[i])。

    这就是状态转移的过程,通过选择这两个选项中的较大值来更新current_sum,从而实现动态规划的“状态更新”。

动态规划特征总结:

  • 状态:以当前位置结尾的最大子数组和(即current_sum)。
  • 状态转移方程current_sum = max(nums[i], current_sum + nums[i])
  • 最优解:通过遍历所有状态(即每个元素为结尾的最大子数组和),找出其中的最大值。

动态规划的优化:

Kadane’s Algorithm只需要常数空间来记录当前的子数组和以及最大子数组和,因此它是空间优化后的动态规划版本。相比于一般的动态规划需要维护一个额外的数组来保存所有子问题的解,Kadane’s Algorithm只需维护两个变量(current_summax_sum),这使得它的空间复杂度为O(1)。

结论:

Kadane’s Algorithm确实属于动态规划的一种,只是它通过非常高效的方式解决了最大子数组和的问题,避免了使用更多的空间来存储中间结果。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/420952.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

巧用工具,Vue 集成 medium-zoom 实现图片缩放

文章目录 巧用工具&#xff0c;Vue 集成 medium-zoom 实现图片缩放介绍medium-zoomVue3集成 medium-zoom 示例Vue2集成 medium-zoom 示例进阶 - 可选参数 巧用工具&#xff0c;Vue 集成 medium-zoom 实现图片缩放 在现代网页开发中&#xff0c;为用户提供良好的视觉体验至关重…

K-Means聚类

聚类的作用&#xff1a; 知识发现 发现事物之间的潜在关系 异常值检测 特征提取 数据压缩的例子 有监督和无监督学习&#xff1a; 有监督&#xff1a; 给定训练集 X 和 标签Y 选择模型 学习&#xff08;目标函数的最优化&#xff09; 生成模型&#xff08;本质上是一组参…

RocketMQ异步报错:No route info of this topic

在SpringBoot中发送RocketMQ异步消息的时候报错了&#xff0c;提示org.apache.rocketmq.client.exception.MQClientException: No route info of this topic, testTopic1 这里给出具体的解决方案 一、Broker模块不支持自动创建topic&#xff0c;并且topic没有被手动创建过 R…

OpenCV 与 YoloV3的结合使用:目标实时跟踪

目录 代码分析 1. YOLO 模型加载 2. 视频加载与初始化 3. 视频帧处理 4. 物体检测 5. 处理检测结果 6. 边界框和类别显示 7. 帧率&#xff08;FPS&#xff09;计算 8. 结果显示与退出 9. 资源释放 整体代码 效果展示 总结 代码分析 这段代码使用 YOLO&#xff08…

Linxu系统:kill命令

1、命令详解&#xff1a; kill命令是用于向进程发送信号&#xff0c;通常用来终止某个指定PID服务进程&#xff0c;kill命令可以发送不同的信号给目标进程&#xff0c;来实现不同的操作&#xff0c;如果不指定信号&#xff0c;默认会发送 TERM 信号&#xff08;15&#xff09;&…

ubuntu 和windows用samba服务器实现数据传输

1&#xff0c;linux安装samba服务器 sudo apt-get install samba samba-common 2&#xff0c;linux 配置权限&#xff0c;修改目录权限&#xff0c;linux下共享的文件权限设置。 sudo chmod 777 /home/lark -R 3. 添加samba用户 sudo smbpasswd -a lark 4&#xff0c;配置共享…

小程序页面整体执行顺序

首先执行 App.onLaunch -> App.onShow其次执行 Component.created -> Component.attached再执行 Page.onLoad -> Page.onShow最后 执行 Component.ready -> Page.onReady 你不知道的小程序系列之生命周期执行顺序

828华为云征文 | Flexus X实例与Harbor私有镜像仓库的完美结合

需要了解 本文章主要讲述在 华为云Flexus X 实例上搭建自己的企业级私有镜像仓库 Harbor&#xff0c;一键部署、搭建高可用安全可靠的容器镜像仓库选择合适的云服务器&#xff1a; 本文采用的是 华为云服务器 Flexus X 实例&#xff08;推荐使用&#xff09;连接方式&#xff1…

ctfshow-PHP特性

web89 <?php include("flag.php"); highlight_file(_FILE_);if(isset($_GET[num])){$num$_GET[num];if(preg_match("/[0-9]/",$num)){die("no no no"); #结束脚本呢执行输出指定信息}if(intval($num)){#把参数转换整数类型echo $flag;} } pr…

用面向对象的方法进行数据分析

项目从两个不同类型的文件&#xff08;文本文件和 JSON 文件&#xff09;读取销售数据&#xff0c;将其封装为 Record 对象&#xff0c;合并数据后&#xff0c;统计每天的销售总额&#xff0c;并通过 pyecharts 库生成一个包含每日销售额的柱状图&#xff08;Bar chart&#xf…

无线感知会议系列【1】【增强无线感知应用的鲁棒性】

前言&#xff1a; 这个是2021年 泛在可信智能感知论坛&#xff0c;汤战勇 &#xff08;西北大学物联网研究院 )教授的 一个讲座《wireless signals like WiFi, RFID and (ultra) sound as a powerful modality for ubiquitous sensing》 参考连接&#xff1a; 4.见微知萌—…

ollama 本地部署

ollama 本地模型部署 下载安装: [link](https://ollama.com/download)下载说明 部署使用在终端查看ollama是否安装完成终端查看ollama 命令说明查看当前支持下载的模型启动对话模式默认情况下&#xff0c;ollama启动了server 的api访问功能 外部 api访问使用postman网页版本for…

什么是Aware注入?

Spring容器可以在Bean初始化的时候&#xff0c;自动注入一些特定信息&#xff08;如beanfactory&#xff09;,使得bean可以轻松的访问其他Bean的实例&#xff0c;简化代码&#xff0c;避免了显式的注入。 Spring提供了很多Aware的接口,如下&#xff1a; 拿其中的BeanFactoryAwa…

全频段覆盖的卫星通信模块-灵活应对多应用场景

LoRa1121是采用SEMTECH的LR1121芯片&#xff0c;这是一款超低功耗、远程LoRa收发器&#xff0c;支持Sub-GHz和全球2.4GHz频谱中的地面ISM频段通信&#xff0c;且支持用于卫星连接的S频段。LoRa1121支持LoRa&#xff0c;(G)FSK调制&#xff0c;Sigfox协议&#xff0c;以及&#…

SRS流媒体服务器从入门到精通(其一,环境搭建)

欢迎诸位来阅读在下的博文~ 在这里&#xff0c;在下会不定期发表一些浅薄的知识和经验&#xff0c;望诸位能与在下多多交流&#xff0c;共同努力! 江山如画&#xff0c;客心如若&#xff0c;欢迎到访&#xff0c;一展风采 文章目录 一、SRS简介二、SRS的应用场景三、环境搭建…

Leetcode - 周赛414

目录 一&#xff0c;3280. 将日期转换为二进制表示 二&#xff0c;3281. 范围内整数的最大得分 三&#xff0c;3282. 到达数组末尾的最大得分 四&#xff0c;3283. 吃掉所有兵需要的最多移动次数 一&#xff0c;3280. 将日期转换为二进制表示 本题就是简单的字符串和整数之…

爆改YOLOv8|利用yolov9的ADown改进卷积Conv-轻量化

1&#xff0c;本文介绍 本文将利用YOLOv9的ADown模块改进卷积。 关于ADown的详细介绍可以看论文&#xff1a;https://arxiv.org/abs/2402.13616 本文将讲解如何将ADown融合进yolov8 话不多说&#xff0c;上代码&#xff01; 2&#xff0c; 将ADown融合进yolov8 2.1 步骤一…

【高中物理】用代码缩写胡克定律公式原理图

用代码缩写胡克定律公式原理图 代码实现了以下功能&#xff1a; 交互式滑块&#xff1a;用户可以通过滑块调整弹簧的弹性系数&#xff08;k&#xff09;、拉力大小&#xff08;F&#xff09;和弹簧的原长&#xff08;l0&#xff09;&#xff0c;实时观察弹簧的伸长和受力变化。…

在VB.net中,TimeSpan有什么属性与方法

标题 在VB.net中&#xff0c;TimeSpan有什么属性与方法 正文 在 VB.NET 中&#xff0c;TimeSpan 结构表示时间间隔&#xff0c;即一段时间&#xff0c;而不表示特定的时间点。TimeSpan 提供了多种属性来获取时间间隔的各个组成部分&#xff0c;以及一些方法来操作这些时间间隔。…

【观察者】设计模式:构建灵活且响应式的软件系统

引言 在软件开发中&#xff0c;我们经常面临需要在多个对象之间进行通信的挑战。特别是当一个对象的状态发生变化时&#xff0c;我们希望所有依赖于这个状态的对象都能自动更新。这就是观察者设计模式大显身手的地方。 简介 观察者模式是一种行为设计模式&#xff0c;它定义…