53.最大子数组和,动态规划+贪心解法!!!
力扣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 定义dp数组的含义,dp[i]为从以下标i结束的连续数组的最大和
2 接着推导出递推公式,想要得到dp[i]有两种途径
第一个就是加上当前元素了,即dp[i] = dp[i - 1] + nums[i]
第二个就是没有将当前元素加到序列中,而是从当前元素开始新的子数组即dp[i] = nums[i]
3 接下来分析一下初始化,一维的dp数字全都初始化为0,这是肯定的,因为dp[i]一开始确实没有一个固定的值
第一个dp[i] = dp[i - 1] + nums[i],所以i要从1开始遍历,不然会访问内存错误,dp[0]需要单独初始化为nums[0]
class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();vector<int> dp(len + 1, 0);dp[0] = nums[0];int result = dp[0];for(int i = 1; i < len; i ++){dp[i] = max(dp[i - 1] + nums[i], nums[i]);if(dp[i] > result) result = dp[i];}return result;}
};``````cpp
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;//最大和int count = 0;//当前和for(int i = 0; i < nums.size(); i ++){count += nums[i];if(count > result){result = count;}if(count < 0) count = 0;}return result;}
};
贪心
贪心是从局部最优推导全局最优
那么这道题的局部最优在哪里呢?
如果 -2 1 在一起,计算起点的时候,一定是从 1 开始计算,因为负数只会拉低总和,这就是局部最优的地方!
所以思路关键在于:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;//最大和int count = 0;//当前和for(int i = 0; i < nums.size(); i ++){count += nums[i];if(count > result){result = count;}if(count < 0) count = 0;}return result;}
};
相关文章:
53.最大子数组和,动态规划+贪心解法!!!
力扣53最大子数组和 题目动态规划贪心 题目 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组中的一个连续部分。 示例 1: 输入:nums…...
python+vue3+onlyoffice在线文档系统实战20240723笔记,项目界面设计和初步开发
经过之前的学习,已经能够正常打开文档了。 目前为止,我们的代码能够实现: 打开文档编辑文档手动保存自动保存虽然功能依然比较少,但是我们已经基本实现了文档管理最核心的功能,而且我们有个非常大的优势,就是支持多人同时在线协同编辑。 现在我们要开发项目,我们得做基…...
谷粒商城实战笔记-72-商品服务-API-属性分组-获取分类属性分组
文章目录 一,后端接口开发Controller层修改接口接口测试 二,前端开发 这一节的内容是开发获取分类属性分组的接口。 一,后端接口开发 Controller层修改接口 修改AttrGroupController接口。 RequestMapping("/list/{catelogId}")p…...
Vue 自定义指令
文章目录 注册局部注册全局注册 钩子钩子参数应用1、按钮权限验证2、自定义用户行为收集指令3、按钮点击防抖4、输入框自动获取焦点5、输入框自动去空字符串6、文字展示不下时展示提示框 注册 局部注册 export default {setup() {/*...*/},directives: {// 在模板中启用 v-fo…...
【python】python图书管理系统_普通用户+管理员菜单(源码+论文)【独一无二】
👉博__主👈:米码收割机 👉技__能👈:C/Python语言 👉公众号👈:测试开发自动化【获取源码商业合作】 👉荣__誉👈:阿里云博客专家博主、5…...
智能路面裂缝检测:基于YOLO和深度学习的全流程实现
引言 路面裂缝检测是维护道路质量和延长道路寿命的重要手段。传统的检测方法往往费时费力且易受人为因素影响。为了提高检测效率和准确性,本文介绍了一种基于深度学习的路面裂缝检测系统。该系统包括用户界面,利用YOLO(You Only Look Once&a…...
C++ unordered_map
1. unordered系列关联式容器 在C98 中, STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,…...
PHP Switch 语句
PHP 中的 switch 语句是一种多路分支语句,它允许一个变量的值对多个代码块进行选择执行。这通常比使用多个 if...elseif...else 语句更清晰、更易于维护。下面将详细介绍 PHP 中 switch 语句的使用方法。 基本语法 switch (n) {case label1:// 如果 n label1&…...
electron 网页TodoList应用打包win桌面软件数据持久化
参考: electron 网页TodoList工具打包成win桌面应用exe https://blog.csdn.net/weixin_42357472/article/details/140648621 electron直接打包exe应用,打开网页上面添加的task在重启后为空,历史没有被保存,需要持久化工具保存之前…...
软件缺陷(Bug)、禅道
目录 软件缺陷的判定标准 软件缺陷的核心内容 构成缺陷的基本要素 缺陷报告 缺陷管理 缺陷的跟踪流程 项目管理工具--禅道 软件在使用过程中存在的任何问题(如:错误、异常等),都叫软件的缺陷,简称bug。 软件缺…...
MySQL客户端命令一节将.sql文件导入MySQL
MySql客户端命令 直接输入SQL语句 使用MySQL客户端连接到服务器之后,可以发送SQL语句到服务器执行,并且以;和\g, \G作为结束不同的结束方式显示内容有所不同** TIPS: ;和\g结尾以表格的形式显示结果\G以行的形式显示结果 在连接到服务器之后…...
[论文笔记] DCA(Dual Chunk Attention)
DCA(Dual Chunk Attention)是一种在自然语言处理模型中用来处理长文本的技术。传统的注意力机制(Attention)在处理长文本时可能会遇到效率和性能瓶颈,因为计算每个单词与其他所有单词之间的关系会随着文本长度的增加而…...
构建查询洞察 UI
本文字数:2631;估计阅读时间:7 分钟 作者:Bucky Schwarz 本文在公众号【ClickHouseInc】首发 我们最近发布了 Query Insights 的初步实现,为 ClickHouse Cloud 用户提供了一种便捷的方法来查看和解释查询日志。该功能对…...
【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十九章 等待队列
i.MX8MM处理器采用了先进的14LPCFinFET工艺,提供更快的速度和更高的电源效率;四核Cortex-A53,单核Cortex-M4,多达五个内核 ,主频高达1.8GHz,2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…...
35.【C语言】详解函数递归
目录: 定义 作用 例子1~3 拓展学习 趣味练习 1.定义:函数自己调用自己(递推回归) int main() {main()return 0; } 这样容易死循环,导致爆栈(Stack Overflow) 所以需要设立限制条件,使执行时越来越接近条…...
【机器学习】智驭未来:机器学习如何重塑制造业的转型与升级
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀目录 🔍1. 引言📒2. 机器学习重塑制造业生产流程🌸预测性维护:减少停机时间,提高设…...
Python爬虫(5) --爬取网页视频
文章目录 爬虫爬取视频指定url发送请求UA伪装请求页面 获取想要的数据解析定位定位音视频位置 存放视频完整代码实现总结 爬虫 Python 爬虫是一种自动化工具,用于从互联网上抓取网页数据并提取有用的信息。Python 因其简洁的语法和丰富的库支持(如 requ…...
【Unity】关于Luban的简单使用
最近看了下Luban导出Excel数据的方式,来记录下 【Unity】关于Luban的简单使用 安装Luban开始使用UnityLubanC# 扩展 安装Luban Luban文档:https://luban.doc.code-philosophy.com/docs/beginner/quickstart 1.安装dotnet sdk 8.0或更高版本sdk 2.githu…...
企业公户验证API如何使用JAVA、Python、PHP语言进行应用
在纷繁复杂的金融与商业领域,确保每笔交易的安全与合规是至关重要的。而企业公户验证API,正是这样一位默默守护的数字卫士,它通过智能化的手段,简化了企业对公账户验证流程,让繁琐的审核变得快捷且可靠。 什么是企业公…...
杰发科技Bootloader(2)—— 基于7840的Keil配置地址
序 在7840的sample代码里面有一个简单的Boot跳转APP的示例 PFlash地址从0开始 DFlash的地址从1000000开始 Boot解析 他的boot地址配置为0 Boot的代码主要是这几行,主要作用就是Flash的跳转 int main(void) {SystemClock_Config();InitDebug();printf("demo…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
从零开始打造 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修改…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
