【算法】动态规划之LeetCode 53.最大子数组和

目录

文章目录

  • **目录**
  • 📑前言
    • 1.题目描述
    • 2. 动态规划法
  • 📑文章末尾


📑前言

本文主要是leetcode题解析,如果有什么需要改进的地方还请大佬指出⛺️

🎬作者简介:大家好,我是青衿🥇
☁️博客首页:CSDN主页放风讲故事
🌄每日一句:努力一点,优秀一点

在这里插入图片描述

1.题目描述

给你一个整数数组 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) 的解法,尝试使用更为精妙的 分治法 求解。

动态规划的空间优化

这题是典型的动态规划题目, 最困难的点在于 dp数组的定义及下标含义用ai代表nums[i], 用f(i)代表以第i个数结尾的「连续子数组的最大和」, 网上也有很多文章介绍了是如何一步步分析来获得定义的过程的, 但我感觉对于新手来说, 可能还是多见一些类似的题目, 获得大量的经验, 这样比较有效果吧, 毕竟想研究动态规划的理论基础还是挺有难度的.

动态规划最重要的思想就是**利用上一个状态, 对于本题而言就是: 到底要不要加上上一个状态f(i-1)的信息, 这完全取决于f(i-1)的正负情况, 这样我们就能得出了动态规划的递推公式: f(i)=max{f(i−1)+ai,ai}

得到了递推公式后就可以编写代码了, 代码中的一个技巧就是对于空间复杂度的优化. 当使用动态规划只需要一个数(并不需要整个dp数组)时, 我们就没必要将整个dp数组都保存下来, 我们只需用变量来记录下我们需要的某个量即可, 这个优化方法在动态规划中还是非常常用的方法, 具体的实现参考代码.

2. 动态规划法

思路(动态规划)   O(n)
状态表示:f[i]表示以nums[i]为结尾的最大连续子数组和。
状态计算:如何确定f[i]的值? 以nums[i]为结尾的连续子数组共分为两种情况:
只有nums[i]一个数,则f[i] = nums[i];
以nums[i]为结尾的多个数,则f[i] = f[i - 1] + nums[i]。
两种情况取最大值,因此状态转移方程为:f[i] = max(f[i - 1] + nums[i], nums[i])。
初始化:f[0] = nums[0]。
最后遍历每个位置的f[i],然后其中的最大值即可。
时间复杂度分析: 只遍历一次数组,O(n)
class Solution {public int maxSubArray(int[] nums) {int n = nums.length;if (n == 0) return 0;int[] dp = new int[n];// base case// 第一个元素前面没有子数组dp[0] = nums[0];// 状态转移方程for (int i = 1; i < n; i++) {dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);}// 得到 nums 的最大子数组int res = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {res = Math.max(res, dp[i]);}return res;}
}  

📑文章末尾

在这里插入图片描述

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

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

相关文章

ThreadLocal 会出现内存泄漏吗?

ThreadLocal ThreadLocal 是一个用来解决线程安全性问题的工具。它相当于让每个线程都开辟一块内存空间&#xff0c;用来存储共享变量的副本。然后每个线程只需要访问和操作自己的共享变量副本即可&#xff0c;从而避免多线程竞争同一个共享资源。它的工作原理很简单&#xff0…

基于Ubuntu20.04安装ROS系统

文章目录 一、ROS简介二、ROS安装三、ROS安装测试四、安装问题解决1. sudo rosdepc init&#xff1a;找不到命令2. ERROR: cannot download default sources list from...3. Command roscore not found...4. Resource not found: roslaunch... 一、ROS简介 ROS是用于编写机器人…

[ubuntu系统下的文本编辑器nano,vim,gedit,文件使用,以及版本更新问题]

文本编辑器概要 在Ubuntu系统下&#xff0c;有许多文本编辑器可供选择&#xff0c;每个编辑器都有其独特的特性和用途。以下是一些常见的文本编辑器&#xff1a; Gedit&#xff1a; 这是Ubuntu默认的文本编辑器&#xff0c;它简单易用&#xff0c;适合基本的文本编辑任务。 安…

取石子

每一堆数量都>1的话可以把合并操作和取石子看成一种操作&#xff0c;总操作数就是sumn-1&#xff0c;为奇数就是Alice先手必胜&#xff0c;哪怕有一堆是2&#xff0c;Bob取后变为1&#xff0c;Alice也可以通过合并操作让1变成>1的数 可以分成两大板块a、b, a中方石子个数…

haproxy高可用集群

高可用集群 Haproxy &#xff1a;他是常用的负载均衡软件 Nginx 支持四层转发&#xff0c;和七层转发 Haproxy 也可以四层和七层转发 LVS的DR发和nat是基于四层还是七层的转&#xff1f; 都基于是四层转发&#xff08…

[SHCTF 2023 校外赛道] pwn

有19道题这么多,不过基本是入门题,都是在骗新生,看这么容易快来PWN吧! week1 四则计算器 这里用危险函数gets读入有个溢出.而且PIE也没开,地址是固定的.而且有后门.直接溢出到ret写上后门即可. from pwn import *p remote(112.6.51.212, 31473) context(archamd64, log_lev…

#stm32整理(二)关于MDK的编译过程及文件类型全解

参考野火开发指南如有侵权即刻删除&#xff0c;只是为了学习交流使用 1、编译 1、编译过程简介 (1&#xff09;编译&#xff0c;MDK 软件使用的编译器是 armcc 和 armasm&#xff0c;它们根据每个 c/c 和汇编源文件编译 成对应的以“.o”为后缀名的对象文件 (Object Code&…

修改el-date-picker宽度

<div style"width: 100%"><el-date-pickerstyle"width:100%"v-model"value"type"datetimerange"start-placeholder"开始日期"end-placeholder"结束日期":default-time"[12:00:00]"value-forma…

Redis队列Stream

1 缘起 项目中处理文件的场景&#xff1a; 将文件处理请求放入队列&#xff0c; 一方面&#xff0c;缓解服务器文件处理压力&#xff1b; 另一方面&#xff0c;可以根据文件大小拆分到不同的队列&#xff0c;提高文件处理效率。 这是Java开发组Leader佳汇提出的文件处理方案&a…

hdlbits系列verilog解答(8位宽移位寄存器)-24

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 这项练习是module_shift移位寄存器的延伸。模块端口不是只有单个引脚,我们现在有以向量作为端口的模块,您将在其上附加线向量而不是普通线网数据。与 Verilog 中的其他位置一样,端口的向量长度不必与连接到它…

Go语言用Resty库编写的音频爬虫代码

目录 一、Go语言与Resty库简介 二、音频爬虫的实现 1、确定抓取目标 2、使用Resty发送HTTP请求 3、解析响应数据 4、下载音频文件 5、并发下载音频文件 三、注意事项 总结 随着互联网的飞速发展&#xff0c;网络爬虫逐渐成为数据获取和分析的重要工具。在音频领域&…

[NSSCTF 2nd] web刷题记录

文章目录 php签到MyBox非预期解预期解 php签到 源代码 <?phpfunction waf($filename){$black_list array("ph", "htaccess", "ini");$ext pathinfo($filename, PATHINFO_EXTENSION);foreach ($black_list as $value) {if (stristr($ext, …

【计算机网络】什么是HTTPS?HTTPS为什么是安全的?

【面试经典题】 前言&#xff1a; HTTP最初的设计就是用于数据的共享和传输&#xff0c;并没有考虑到数据的安全性&#xff0c;如窃听风险&#xff0c;篡改风险和冒充风险。HTTPS是在 HTTP 的基础上引入了一个加密层。HTTPS通过数据加密&#xff0c;数据完整性检验和身份认证…

BUUCTF_练[CISCN2019 华北赛区 Day1 Web5]CyberPunk

[CISCN2019 华北赛区 Day1 Web5]CyberPunk 文章目录 [CISCN2019 华北赛区 Day1 Web5]CyberPunk掌握知识解题思路代码分析paylaod的构建正式解题 关键paylaod 掌握知识 ​ php伪协议读取文件&#xff1b;源码泄露hint &#xff1b;代码审计 发现二次注入点&#xff1b;SQL语句的…

【Unity小技巧】可靠的相机抖动及如何同时处理多个震动(附项目源码)

文章目录 每篇一句前言安装虚拟相机虚拟相机震动测试代码控制震动清除震动控制震动的幅度和时间 两个不同的强弱震动同时发生源码完结 每篇一句 围在城里的人想逃出来&#xff0c;站在城外的人想冲进去&#xff0c;婚姻也罢&#xff0c;事业也罢&#xff0c;人生的欲望大都如此…

从 malloc 分配大块内存失败 来简看 linux 内存管理

文章目录 背景Glibc MallocMalloc 分配大块内存失败原因Overcommit_memory 实现OOM (Out Of Memory) 的实现 背景 应用进程 malloc 返回了null&#xff0c;但是观察到的os 的free内存还有较大的余量 &#xff0c;很奇怪为什么会这样&#xff1f; 不可能是oom导致的&#xff0…

【2023Mathorcup大数据】B题 电商零售商家需求预测及库存优化问题 python代码解析

【2023Mathorcup大数据】B题 电商零售商家需求预测及库存优化问题 python代码解析 1 题目 2023 年MathorCup 高校数学建模挑战赛——大数据竞赛赛道B&#xff1a;电商零售商家需求预测及库存优化问题电商平台存在着上千个商家&#xff0c;他们会将商品货物放在电商配套的仓库…

企业金蝶KIS软件服务器中了locked勒索病毒怎么办,勒索病毒解密

最近一段时间&#xff0c;网络上的locked勒索病毒又开始了新一波的攻击&#xff0c;给企业的正常生产生活带来了严重影响。经过最近一段时间云天数据恢复中心对locked勒索病毒的解密&#xff0c;为大家整理了以下有关locked勒索病毒的相关信息。近期locked勒索病毒主要攻击金蝶…

小白如何在一个月写一篇论文(中文核心,SCI)

小白如何半年发3篇sci的我教你如何快速“水”一篇sci论文_哔哩哔哩_bilibili 计算机视觉&#xff0c;cv领域 半年发3篇sci的我教你如何快速“水”一篇sci论文 计算机视觉(辅导 SCI EI 核心) 微信&#xff1a;whbwqq123或主页加up 小白如何快速写出一篇论文并成功发表&…