53. 最大子数组和
文章目录
- 题目描述
- 暴力法
- 动态规划法
- 分治法
- 参考文献
题目描述
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
暴力法
class Solution {public int maxSubArray(int[] nums) {if(nums.length==1){return nums[0];}int max=nums[0];int tmp;for(int i=0;i<nums.length;i++){tmp=0;for(int j=i;j<nums.length;j++){tmp=tmp+nums[j];if(tmp>max){max=tmp;}}}return max;}
}

动态规划法

class Solution {public int maxSubArray(int[] nums) {int[] dp=new int[nums.length];dp[0]=nums[0];int res=dp[0];for(int i=1;i<nums.length;i++){dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);res=Math.max(res,dp[i]);}return res;}
}
分治法
理解起来好复杂,暂时不看了。
参考文献
点击跳转
https://www.bilibili.com/video/BV1xa411A76q?p=11&vd_source=0b5b75024b90934f32850d5e16883515
相关文章:
53. 最大子数组和
文章目录题目描述暴力法动态规划法分治法参考文献题目描述 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入&…...
基于Java+SpringBoot+SpringCloud+Vue前后端分离医院管理系统设计与实现
博主介绍:✌全网粉丝3W,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建、毕业项目实战、项目定制✌ 博主作品:《微服务实战》专栏是本人的实战经验总结,《S…...
QT基础入门【环境配置篇】linux桌面QT开发环境的构建以及问题解决
目录 一、下载QT的安装包 二、安装 1.执行以下命令开始安装 2.选择配置 三、启动...
Linux系统之部署企业内部静态导航页
Linux系统之部署企业内部静态导航页 一、本次实践目的二、检查本地系统环境1.检查系统版本2.检查内核版本三、下载静态导航页资源包1.创建下载目录2.下载资源包四、安装apache服务1.安装httpd2.复制网页文件3.重启httpd服务4.检查httpd服务状态五、访问导航页六、修改导航页网站…...
2023备战金三银四,Python自动化软件测试面试宝典合集(四)
接上篇:11、点击塞钱进红包,选择使用新卡付款,按照流程添加新卡,此时同样需要考虑金额>新卡余额,金额<新卡余额,金额新卡余额三种情况12、使用指纹确认付款(正确的/不正确的指纹)13、使用密码确认付款…...
算法训练营 day43 动态规划 不同路径 不同路径 II
算法训练营 day43 动态规划 不同路径 不同路径 II 不同路径 62. 不同路径 - 力扣(LeetCode) 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达…...
关联查询的SQL有几种情况
1、内连接:inner join … on 结果:A表 ∩ B表 2、左连接:A left join B on (2)A表全部 (3)A表- A∩B 3、右连接:A right join B on (4)B表全部 &#…...
查缺补漏三:事务隔离级别
什么是事务? 事务就是一组操作的集合,事务将整组操作作为一个整体,共同提交或者共同撤销 这些操作只能同时成功或者同时失败,成功即可提交事务,失败就执行事务回滚 MySQL的事务默认是自动提交的,一条语句执…...
没有她的通讯录(C语言实现)
🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 收藏⭐️ 留言📝 📣系列专栏:夏目的C语言宝藏 💬总结:希望你看完之…...
Spring Security 从入门到精通
前言 Spring Security 是 Spring 家族中的一个安全管理框架。相比与另外一个安全框架Shiro,它提供了更丰富的功能,社区资源也比Shiro丰富。 一般来说中大型的项目都是使用SpringSecurity 来做安全框架。小项目有Shiro的比较多,因为相比与Spr…...
微信小程序Springboot vue停车场车位管理系统
系统分为用户和管理员两个角色 用户的主要功能有: 1.用户注册和登陆系统 2.用户查看系统的公告信息 3.用户查看车位信息,在线预约车位 4.用户交流论坛,发布交流信息,在线评论 5.用户查看地图信息,在线导航 6.用户查看个…...
看完这篇 教你玩转渗透测试靶机vulnhub——Hack Me Please: 1
Vulnhub靶机Hack Me Please: 1渗透测试详解Vulnhub靶机介绍:Vulnhub靶机下载:Vulnhub靶机安装:Vulnhub靶机漏洞详解:①:信息收集:②:漏洞利用③:获取反弹shell:④&#x…...
nodejs+vue地铁站自动售票系统-火车票售票系统vscode
地铁站自动售票系统主要包括个人中心、地铁线路管理、站点管理、购票信息管理、乘坐管理、用户信息管理等多个模块。它使用的是前端技术:nodejsvueelementui 前后端通讯一般都是采取标准的JSON格式来交互。前端技术:nodejsvueelementui,视图层其实质就是…...
Spring Security in Action 第十二章 OAuth 2是如何工作的?
本专栏将从基础开始,循序渐进,以实战为线索,逐步深入SpringSecurity相关知识相关知识,打造完整的SpringSecurity学习步骤,提升工程化编码能力和思维能力,写出高质量代码。希望大家都能够从中有所收获&#…...
天工开物 #5 我的 Linux 开发机
首先说一下结论:最终我选择了基于 Arch Linux[1] 的 Garuda Linux[2] 发行版作为基础来搭建自己的 Linux 开发机。Neofetch 时刻发行版的选择在上周末的这次折腾里,我一共尝试了 Garuda Linux 发行版,原教旨的 Arch Linux 发行版,…...
【沁恒WCH CH32V307V-R1开发板输出DAC实验】
【沁恒WCH CH32V307V-R1开发板输出DAC实验】1. 前言2. 软件配置2.1 安装MounRiver Studio3. DAC项目测试3.1 打开DAC工程3.2 编译项目4. 下载验证4.1 接线4.2 演示效果5. 小结1. 前言 数字/模拟转换模块(DAC),包含 2 个可配置 8/12 位数字输入…...
Linux进程控制详解
目录前言一、进程创建1.1 fork函数初识1.2 写时拷贝1.3 fork常规用法1.4 fork调用失败的原因二、进程终止2.1 进程终止时,操作系统做了什么??2.2 进程终止的常见方式有哪些??2.3 如何用代码终止一个进程三、进程等待3.…...
C语言深度剖析之程序环境和预处理
1.程序的翻译环境和执行环境 第一种是翻译环境,在这个环境中源代码被转换为可执行的机器指令 第二种是执行环境,它用于实际执行代码 2.翻译环境 分为四个阶段 预编译阶段 ,编译,汇编,链接 程序编译过程:多个…...
【Spark分布式内存计算框架——Spark Core】9. Spark 内核调度(上)
第八章 Spark 内核调度 Spark的核心是根据RDD来实现的,Spark Scheduler则为Spark核心实现的重要一环,其作用就是任务调度。Spark的任务调度就是如何组织任务去处理RDD中每个分区的数据,根据RDD的依赖关系构建DAG,基于DAG划分Stag…...
Vulkan教程(15): Graphics pipeline之Render passes(渲染通道)
Vulkan官方英文原文: https://vulkan-tutorial.com/Drawing_a_triangle/Graphics_pipeline_basics/Render_passes对应的Vulkan技术规格说明书版本: Vulkan 1.3.2Setup设置Before we can finish creating the pipeline, we need to tell Vulkan about the…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
