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

【LeetCode Hot100】最大子数组和|动态规划/贪心,Java实现!图解+代码,小白也能秒懂!

💻 [LeetCode Hot100] 最大子数组和|动态规划/贪心,Java实现!图解+代码,小白也能秒懂!

✏️本文对应题目链接:最大子数组和


📌 题目描述

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6

🧠 解题思路(图文分解)

❗ 核心难点

如何在O(n)时间复杂度内找到最大和的连续子数组?


方法一:动态规划(贪心思想)✨

关键步骤:

  1. 定义状态currentMax 表示以当前元素结尾的子数组的最大和
  2. 状态转移
    • 如果 currentMax > 0 → 当前元素加入子数组
    • 如果 currentMax ≤ 0 → 从当前元素重新开始子数组
  3. 更新全局最大值globalMax 记录遍历过程中的最大值

图解动态规划

输入数组:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

遍历过程:

i=0: currentMax=-2 → globalMax=-2
i=1: currentMax=max(1, -2+1)=1 → globalMax=1
i=2: currentMax=max(-3, 1-3)=-2 → globalMax=1
i=3: currentMax=max(4, -2+4)=4 → globalMax=4
i=4: currentMax=max(-1, 4-1)=3 → globalMax=4
i=5: currentMax=max(2, 3+2)=5 → globalMax=5
i=6: currentMax=max(1, 5+1)=6 → globalMax=6
i=7: currentMax=max(-5, 6-5)=1 → globalMax=6
i=8: currentMax=max(4, 1+4)=5 → globalMax=6

最终结果:

globalMax = 6

🚀 代码实现

class Solution {public int maxSubArray(int[] nums) {int currentMax = nums[0]; // 当前最大子数组和int globalMax = nums[0];  // 全局最大子数组和for (int i = 1; i < nums.length; i++) {// 动态规划核心逻辑:选择继续累加或重新开始currentMax = Math.max(nums[i], currentMax + nums[i]);// 更新全局最大值globalMax = Math.max(globalMax, currentMax);}return globalMax;}
}

💡 复杂度分析

  • 时间复杂度:O(n) → 只需遍历数组一次
  • 空间复杂度:O(1) → 仅使用常数空间

方法二:分治法(进阶思路)

关键思路:将数组分成左右两部分,分别求解左半部分、右半部分和跨越中间的最大子数组和。

class Solution {public int maxSubArray(int[] nums) {return divideAndConquer(nums, 0, nums.length - 1);}private int divideAndConquer(int[] nums, int left, int right) {if (left == right) return nums[left];int mid = left + (right - left) / 2;int leftMax = divideAndConquer(nums, left, mid);int rightMax = divideAndConquer(nums, mid + 1, right);int crossMax = maxCrossingSum(nums, left, mid, right);return Math.max(Math.max(leftMax, rightMax), crossMax);}private int maxCrossingSum(int[] nums, int left, int mid, int right) {int leftSum = Integer.MIN_VALUE;int currentSum = 0;for (int i = mid; i >= left; i--) {currentSum += nums[i];leftSum = Math.max(leftSum, currentSum);}int rightSum = Integer.MIN_VALUE;currentSum = 0;for (int i = mid + 1; i <= right; i++) {currentSum += nums[i];rightSum = Math.max(rightSum, currentSum);}return leftSum + rightSum;}
}

🌟 总结要点

贪心思想核心:当累计和为负数时,立即放弃当前子序列
分治法适用场景:大数据量分布式计算(时间复杂度O(n log n))
适用场景:股票买卖、信号处理等求最大连续区间和问题


相关文章:

【LeetCode Hot100】最大子数组和|动态规划/贪心,Java实现!图解+代码,小白也能秒懂!

&#x1f4bb; [LeetCode Hot100] 最大子数组和&#xff5c;动态规划/贪心&#xff0c;Java实现&#xff01;图解代码&#xff0c;小白也能秒懂&#xff01; ✏️本文对应题目链接&#xff1a;最大子数组和 &#x1f4cc; 题目描述 给定一个整数数组 nums&#xff0c;找到一个…...

【Go语言快速上手】第二部分:Go语言进阶之网络编程

文章目录 前言&#xff1a;网络编程一、TCP/UDP 编程&#xff1a;net 包的使用1. TCP 编程1.1 TCP 服务器1.2 TCP 客户端 2. UDP 编程2.1 UDP 服务器2.2 UDP 客户端 二、HTTP 编程&#xff1a;net/http 包的使用&#xff0c;编写 HTTP 服务器和客户端2.1 HTTP 服务器2.2 HTTP 客…...

AI法理学与责任归属:技术演进下的法律重构与伦理挑战

文章目录 引言:智能时代的新型法律困境一、AI技术特性对传统法理的冲击1.1 算法黑箱与可解释性悖论1.2 动态学习系统的责任漂移1.3 多智能体协作的责任稀释二、AI法理学的核心争议点2.1 法律主体资格认定2.2 因果关系的技术解构2.3 过错标准的重新定义三、责任归属的实践案例分…...

Linux探秘坊-------8.进程详解

1.概念详解 1.运行&&阻塞&&挂起 内容基础&#xff1a;方框中的就是调度队列&#xff0c;是一个 双向队列&#xff0c;每一个元素是PCB其对应的代码数据 1.运行 只要进程 在调度队列中&#xff0c;进程的状态就是运行&#xff08;running&#xff09;. 2.阻塞…...

C#使用文件读写操作实现仙剑五前传称号存档修改

手把手教学仙剑五前传 称号存档修改器 首先找到 Pal5Q所在目录的save\global.sav 文件,这是一个只有488字节的文件,这里存放称号对应的编号ID,以及是否已获得该称号,1为已获取称号,0为未获取称号 [称号:是否获取]这是一个键值对 称号的编号ID是一个Int32数字,使用C#的方法Bi…...

Kubernetes知识点总结(十)

什么是 K8s 的 namespace&#xff1f; 在 K8s 中&#xff0c;Namespace&#xff08;名字空间&#xff09;提供了一种机制&#xff0c;将同一集群中的资源划分为相互隔离的组&#xff0c; 是在多个用户之间划分集群资源的一种方法。 名字空间作用域仅针对带有名字空间的对…...

【达梦数据库】disql工具参数绑定

前言 在达梦数据库的使用过程中尽管管理工具很好用&#xff0c;但是命令行工具还是有着得天独厚的优势&#xff0c;但是在参数绑定方面就没有管理工具做的更加完美&#xff0c;现在就汇总下disql 工具参数绑定的常用几种方式 disql 参数绑定 使用 ? select * from v$dm_in…...

箭头函数的this指向谁

先看1个重要原则&#xff1a; 由Vue管理的函数&#xff0c;一定不要写箭头函数&#xff0c;箭头函数的this就不再是Vue实例了 箭头函数的 this 指向在定义时确定&#xff0c;继承自外层作用域&#xff08;即定义时的上下文&#xff09;的 this&#xff0c;且无法通过 call、app…...

Node.js技术原理分析系列——Node.js调试能力分析

本文由体验技术团队屈金雄原创。 Node.js 是一个开源的、跨平台的 JavaScript 运行时环境&#xff0c;它允许开发者在服务器端运行 JavaScript 代码。Node.js 是基于 Chrome V8引擎构建的&#xff0c;专为高性能、高并发的网络应用而设计&#xff0c;广泛应用于构建服务器端应…...

网络基础 【UDP、TCP】

1.UDP 首先我们学习UDP和TCP协议 要从这三个问题入手 1.报头和有效载荷如何分离、有效载荷如何交付给上一层的协议&#xff1f;2.认识报头3.学习该协议周边的问题 UDP报头 UDP我们先从示意图来讲解&#xff0c;认识报头。 UDP协议首部有16位源端口号&#xff0c;16位目的端…...

python旅游推荐系统+爬虫+可视化(协同过滤算法)

✅️基于用户的协同过滤算法 ✅️有后台管理 ✅️2w多数据集 这个旅游数据分析推荐系统采用了Python语言、Django框架、MySQL数据库、requests库进行网络爬虫开发、机器学习中的协同过滤算法、ECharts数据可视化技术&#xff0c;以实现从网站抓取旅游数据、个性化推荐和直观展…...

数据结构 树的存储和遍历

一、树的定义 树的定义 树型结构是⼀类重要的⾮线性数据结构。 • 有⼀个特殊的结点&#xff0c;称为根结点&#xff0c;根结点没有前驱结点。 • 除根结点外&#xff0c;其余结点被分成M个互不相交的集合T1 、T2 、...、Tm T&#xff0c;其中每⼀个集合⼜是⼀棵树&#xff0c…...

《解锁自然语言处理:让公众正确拥抱AI语言魔法》

在当今数字化浪潮中&#xff0c;自然语言处理&#xff08;NLP&#xff09;技术作为人工智能领域的璀璨明珠&#xff0c;正以惊人的速度融入我们的生活。从智能语音助手到智能客服&#xff0c;从机器翻译到内容创作辅助&#xff0c;NLP技术无处不在。然而&#xff0c;如同任何强…...

qt实习总结

创建一个滑动条 QSlider *slider new QSlider(Qt::Vertical); //创建一个垂直方向的 进度条 带有上下箭头的输入框 QSpinBox 提供了一个带有上下箭头的输入框 垂直 水平怎么说 horizontal vetical 布局知识 BtnLayout->addWidget(AmendBtn); BtnLayout->addWidg…...

HTTP的“对话”逻辑:请求与响应如何构建数据桥梁?

一、前言 作为现代互联网通信的基石&#xff0c;HTTP协议定义了客户端与服务器之间的“对话规则”。每一次网页加载、API调用或文件传输的背后&#xff0c;都离不开精心构造的HTTP请求与响应。请求中封装了用户的意图——从请求方法、资源路径到提交的数据&#xff1b;响应则承…...

Docker 镜像标签使用

写在前面 当使用命令 docker pull mysql 拉取镜像时&#xff0c;其实等价于如下命令 docker pull mysql:latest latest 是默认的标签&#xff0c;字面上理解为最新版本的镜像&#xff0c;实质上 latest 只是镜像的标签名称&#xff0c;跟具体某个版本号地位一样&#xff0c;…...

C#异步/多线程编程中Task对象强大的功能介绍。

在 C# 的异步编程中&#xff0c;Task 是一个非常重要的类&#xff0c;它表示一个异步操作。Task 类提供了许多方法&#xff0c;用于管理、控制和组合异步操作。以下是 Task 类中一些常用方法的详细讲解及其功能。 1. Task.Run 功能&#xff1a;将指定的代码块调度到线程池中异步…...

DDD聚合在 ASP.NET Core中的实现

在ASP.NET Core中实现DDD&#xff08;领域驱动设计&#xff0c;Domain-Driven Design&#xff09;聚合通常涉及到几个关键步骤&#xff0c;包括定义领域模型、实现领域服务、使用仓储模式等。以下是如何在ASP.NET Core应用中实现DDD聚合的一些步骤和示例。 1. 定义领域模型 首…...

docker push镜像到阿里云

阿里云账号 阿里云-计算&#xff0c;为了无法计算的价值 开通个人镜像容器 进入控制台&#xff0c;试用容器 实例列表界面 点击上图中的个人&#xff0c;个人版特性 创建个人版&#xff1a; 个人版实例界面&#xff1a; 设置密码 个人版实例&#xff1a; 创建镜像仓库 如上…...

移动通信发展史

概念解释 第一代网络通信 1G 第二代网络通信 2G 第三代网络通信 3G 第四代网络通信 4G 4g网络有很高的速率和很低的延时——高到500M的上传和1G的下载 日常中的4G只是用到了4G技术 运营商 移动-从民企到国企 联通-南方教育口有人 电信 铁通&#xff1a;成立于 2000 年…...

Transformer笔记

Transformer笔记 文章目录 Transformer笔记模型架构核心技术多头注意力机制概念数学概念单头注意力机制代码 基于位置的前馈网络残差连接和层规范化 编码器解码器 特点&#xff1a;Transformer模型完全基于注意力机制&#xff0c;没有任何卷积层或循环神经网络。之前Transforme…...

【学习资源】时间序列数据分析方法(1)

时间序列数据分析是一个有趣的话题&#xff0c;让我们多花一些时间来研究。此篇为第一篇文章。主要介绍特征提取方法、深度学习时序数据分析模型、参考资源。期望能帮助大家解决工业领域的相关问题。 1 特征提取方法&#xff1a;信号处理 (来源:INTELLIGENT FAULT DIAGNOSIS A…...

PHP 文件与目录操作

PHP 学习资料 PHP 学习资料 PHP 学习资料 在 PHP 编程中&#xff0c;文件与目录操作是一项基础且重要的技能。无论是处理用户上传文件、生成日志&#xff0c;还是管理项目中的各类资源&#xff0c;都离不开对文件和目录的操作。PHP 提供了丰富的内置函数&#xff0c;方便开发…...

PostgreSQL认证指南

PostgreSQL 作为一款强大的开源关系型数据库&#xff0c;深受开发者和企业的青睐。获得 PostgreSQL 专家认证&#xff0c;不仅能提升个人在数据库领域的专业能力&#xff0c;还能为职业发展增添有力筹码。下面为大家详细介绍 PostgreSQL 专家认证的学习路径。 一、深入理解基础…...

hive全量迁移脚本

#!/bin/bash #场景&#xff1a;数据在同一库下&#xff0c;并且hive是内部表&#xff08;前缀的hdfs地址是相同的&#xff09;#1.读取一个文件&#xff0c;获取表名#echo "时间$dt_jian_2-------------------------" >> /home/hadoop/qianyi_zengliang/rs.txt#…...

Qt5开发入门指南:从零开始掌握跨平台开发

目录 Qt框架概述 开发环境搭建 基础语法与核心机制 第一个Qt窗口程序 常见问题解答 一、Qt框架概述 1.1 什么是Qt&#xff1f; Qt是一个1995年由挪威Trolltech公司开发的跨平台C图形用户界面应用程序框架。最新Qt5版本主要包含&#xff1a; GUI模块&#xff1a;支持Wind…...

WPF的Prism框架的使用

安装Prism.DryIoc库&#xff1a; Prism的区域和模块化&#xff1a; 一个区域可以显示一个用户控件 一个模块就是一个项目&#xff0c;也就是一个类库 动态切换用户控件的案例&#xff1a; <Grid><Grid.RowDefinitions><RowDefinition Height"auto"…...

【机器学习】线性回归 线性回归模型的损失函数 MSE RMSE MAE R方

【机器学习系列】 KNN算法 KNN算法原理简介及要点 特征归一化的重要性及方式线性回归算法 线性回归与一元线性回归 线性回归模型的损失函数 多元线性回归 多项式线性回归 线性回归模型的损失函数 V1.0损失函数的计算方法损失函数的分类MSE (Mean Squared Error)RMSE (Root Mea…...

服务器部署DeepSeek,通过Ollama+open-webui部署

1. 安装ollama 1.1. linux 安装 Ollama是目前常用的AI模式部署的第三方工具&#xff0c;能一键部署deepSeek Ollama官方网址https://ollama.com/ 选择Download下载对应的服务版本 服务器选择Linux&#xff0c;下面是下载代码 curl -fsSL https://ollama.com/install.…...

Java 大视界 -- 开源社区对 Java 大数据发展的推动与贡献(91)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

【Vue3源码解析】应用实例创建及页面渲染

下载源码 git clone https://github.com/vuejs/core.git写该文章时的Vue版本为&#xff1a; "version": "3.5.13",这里要注意 pnpm 的版本不能太低&#xff0c;我此时的版本为 9.15.4。更新 pnpm 版本&#xff1a; npm install -g pnpm然后安装依赖&…...

云原生AI Agent应用安全防护方案最佳实践(上)

当下&#xff0c;AI Agent代理是一种全新的构建动态和复杂业务场景工作流的方式&#xff0c;利用大语言模型&#xff08;LLM&#xff09;作为推理引擎。这些Agent代理应用能够将复杂的自然语言查询任务分解为多个可执行步骤&#xff0c;并结合迭代反馈循环和自省机制&#xff0…...

人工智能 - 主动视觉可能就是你所需要的:在双臂机器人操作中探索主动视觉

AV-ALOHA 系统使用用于 AV 的 VR 耳机实现直观的数据收集&#xff0c;并且 用于作的 VR 控制器或引线臂。这有助于捕捉全身和头部 远程作我们的真实和模拟系统的运动&#xff0c;记录来自 6 个的视频 不同的摄像头&#xff0c;并为我们的 AV 仿制学习策略提供训练数据。 加州大…...

Ubuntu 下 systemd 介绍

系列文章目录 Linux内核学习 Linux 知识&#xff08;1&#xff09; Linux 知识&#xff08;2&#xff09; WSL Ubuntu QEMU 虚拟机 Linux 调试视频 PCIe 与 USB 的补充知识 vscode 使用说明 树莓派 4B 指南 设备驱动畅想 Linux内核子系统 Linux 文件系统挂载 QEMU 通过网络实现…...

两个实用且热门的 Python 爬虫案例,结合动态/静态网页抓取和反爬策略,附带详细代码和实现说明

在这个瞬息万变的世界里&#xff0c;保持一颗探索的心&#xff0c;永远怀揣梦想前行。即使有时会迷失方向&#xff0c;也不要忘记内心深处那盏指引你前进的明灯。它代表着你的希望、你的信念以及对未来的无限憧憬。每一个不曾起舞的日子&#xff0c;都是对生命的辜负&#xff1…...

Softing线上研讨会 | 自研还是购买——用于自动化产品的工业以太网

| 线上研讨会时间&#xff1a;2025年1月27日 16:00~16:30 / 23:00~23:30 基于以太网的通信在工业自动化网络中的重要性日益增加。设备制造商正面临着一大挑战——如何快速、有效且经济地将工业以太网协议集成到其产品中。其中的关键问题包括&#xff1a;是否只需集成单一的工…...

Jetson Agx Orin平台preferred_stride调试记录--1924x720图像异常

1.问题描述 硬件: AGX Orin 在Jetpack 5.0.1和Jetpack 5.0.2上测试验证 图像分辨率在1920x720和1024x1920下图像采集正常 但是当采集图像分辨率为1924x720视频时,图像输出异常 像素格式:yuv_uyvy16 gstreamer命令如下 gst-launch-1.0 v4l2src device=/dev/video0 ! …...

从2025年起:数字化建站PHP 8.1应成为建站开发的基准线

在数字化浪潮席卷全球的今天,PHP语言仍然保持着Web开发领域的核心地位。根据W3Techs最新统计,PHP驱动着全球78.9%的已知服务端网站。当时间指向2025年,这个拥有28年历史的编程语言将迎来新的发展里程碑——PHP 8.1版本应成为网站开发的最低基准要求,这不仅是技术迭代的必然…...

电动汽车电池监测平台系统设计(论文+源码+图纸)

1总体设计 本次基于单片机的电池监测平台系统设计&#xff0c;其整个系统架构如图2.1所示&#xff0c;其采用STC89C52单片机作为控制器&#xff0c;结合ACS712电流传感器、TLC1543模数转换器、LCD液晶、DS18B20温度传感器构成整个系统&#xff0c;在功能上可以实现电压、电流、…...

20240914 天翼物联 笔试

文章目录 1、行测知识1.11.21.31.41.51.61.71.81.91.101.111.121.131.141.152、专业知识2.12.22.32.42.52.62.72.82.92.102.112.122.132.142.153、编程题3.13.2岗位:嵌入式开发工程师(上海) 题型:15 道行测知识,15 道专业知识,2 道编程题 注意:本文章暂无解析,谨慎分…...

前端高级面试题

以下是一些前端高级面试可能涉及到的内容: 一、前端工程化 如何构建一个适合大型团队的前端代码规范和构建流程? 答案: 代码规范方面: 使用ESLint结合Prettier来统一JavaScript和CSS(包括预处理器如Sass或Less)的语法风格。例如,规定变量命名采用驼峰命名法,函数名要有…...

【nvidia】NCCL禁用P2P后果权衡

通信bound还是计算bound&#xff1f; 计算bound场景&#xff1a; 模型参数量较小&#xff08;如参数量未超出单卡显存容量&#xff0c;使用纯数据并行&#xff09;或计算密度极高&#xff08;如大batch size下的矩阵运算&#xff09;时&#xff0c;A100的计算能力&#xff08…...

哈希表(C语言版)

文章目录 哈希表原理实现(无自动扩容功能)代码运行结果 分析应用 哈希表 如何统计一段文本中&#xff0c;小写字母出现的次数? 显然&#xff0c;我们可以用数组 int table[26] 来存储每个小写字母出现的次数&#xff0c;而且这样处理&#xff0c;效率奇高。假如我们想知道字…...

unity学习46:反向动力学IK

目录 1 正向动力学和反向动力学 1.1 正向动力学 1.2 反向动力学 1.3 实现目标 2 实现反向动力 2.1 先定义一个目标 2.2 动画层layer&#xff0c;需要加 IK pass 2.3 增加头部朝向代码 2.3.1 专门的IK方法 OnAnimatorIK(int layerIndex){} 2.3.2 增加朝向代码 2.4 …...

夜莺监控发布 v8.beta5 版本,优化 UI,新增接口认证方式便于鉴权

以防读者不了解夜莺&#xff0c;开头先做个介绍&#xff1a; 夜莺监控&#xff0c;英文名字 Nightingale&#xff0c;是一款侧重告警的监控类开源项目。类似 Grafana 的数据源集成方式&#xff0c;夜莺也是对接多种既有的数据源&#xff0c;不过 Grafana 侧重在可视化&#xff…...

asio的使用

1、下载 性能测试&#xff1a;https://github.com/huyuguang/asio_benchmark 2、基本使用 2.1 TCP 1、客户端&#xff1a; 2、服务端&#xff1a; 2.2 UDP单揪 boost的asio接收单路大数据量udp包的方法 1、发送&#xff1a; 2、接收&#xff1a; #include "Circled…...

PHP语法完全入门指南:从零开始掌握动态网页

本文专为零基础新手设计,通过5000字详细讲解带你系统学习PHP语法。包含环境搭建、基础语法、实战案例,并附20+代码示例。阅读后你将能独立开发简单动态网页! 一、PHP开发环境搭建(新手必看) 1.1 为什么需要搭建环境? PHP是服务器端脚本语言,需要运行在服务器环境中。推…...

WPF快速创建DeepSeek本地自己的客户端-基础思路版本

开发工具&#xff1a;VS 2015 开发环境&#xff1a;.Net 4.0 使用技术&#xff1a;WPF 本篇文章内容&#xff1a; 本地部署DeepSeek以后一般使用网页工具&#xff08;如Chatbox&#xff09;或者DOS窗口与其对话。本篇文章使用WPF创建一个基础版的对话工具。 一、搭建本地DeepS…...

Win7本地化部署deepseek-r1等大模型详解

参考链接 在Windows 7操作系统&#xff0c;基于llama.cpp本地化部署 deepseek-r1模型的方法 2025-02-08 2G内存Windows7运行deepseek-r1:1.5b 这两个链接写的可能不够详细&#xff0c;有同学私信问实现过程&#xff0c;这里进一步解释一下。 一、准备 需要准备的大模型、工具…...

分享一个解梦 Chrome 扩展 —— 周公 AI 解梦

一、插件简介 周公 AI 解梦是一款基于 Chrome 扩展的智能解梦工具&#xff0c;由灵机 AI 提供技术支持。它能运用先进的 AI 技术解析梦境含义&#xff0c;为用户提供便捷、智能的解梦服务。无论你是对梦境充满好奇&#xff0c;还是想从梦境中获取一些启示&#xff0c;这款插件都…...