LeetCode:53. 最大子数组和 - Python
问题描述:
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
提示:
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
问题分析:
最近又遇到的老题目,很简单大家都知道是dp,但是如果真的是在面试环境上紧张了也许就漏了部分条件,不能AC,所以平时的基本功还是要打扎实的。具体思路:
假设dp[i]表示以数组nums[i]结尾的最大子数组和,那么:dp[i]=max{nums[i], dp[i−1]+nums[i]},解释:dp[i] 的值很显然有两种情况,第1种情况:为上一个状态dp[i−1] 加上当前值nums[i],第2种情况:从当前值nums[i]重新起一个序列(重新开始),这两个种情况选择哪个呢?咱们求的最值吗?所以二者选取最大值。最后把整个dp遍历一般获取最大值即可。
Python3实现:
# @Time :2023/08/24
# @Author :Liu
# 动态规划class Solution:def maxSubArray(self, nums):size = len(nums)if size == 0: return 0dp = [0 for _ in range(size)]dp[0] = nums[0]for i in range(1, size):dp[i] = max(nums[i], dp[i-1] + nums[i])return max(dp)
举一反三:
问题来了,可能很多面试官不按照这个讨论出来牌,如果把题目最后求解的要求改成子数组和的绝对值最大值那?仔细想想也不难,在维持一个和最小dp就可以了,最后结合两个dp的结果返回。
Python3实现:
# @Time :2023/08/24
# @Author :Liu
# 动态规划class Solution:def maxSubArray2(self, nums):size = len(nums)if size == 0: return 0dpmax = [0 for _ in range(size)]dpmin = [0 for _ in range(size)]dpmax[0] = nums[0]dpmin[0] = nums[0]for i in range(1, size):dpmax[i] = max(nums[i], dpmax[i - 1] + nums[i])dpmin[i] = min(nums[i], dpmin[i - 1] + nums[i])return max(abs(max(dpmax)), abs(min(dpmin)))if __name__ == '__main__':solu = Solution()nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4, -10]print(solu.maxSubArray(nums)) # [-5, 4, -10] 11
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。
题目链接:https://leetcode.cn/problems/maximum-subarray/description/
参考链接:https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
相关文章:
LeetCode:53. 最大子数组和 - Python
53. 最大子数组和 问题描述: 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入:nums [-…...
网站建设 之 react usestate
react着重在于“不可变动” 如果变动了怎么办呢?那就整个新的 局部变量/函数/jsx-》state/props-〉ref,依次越来越难变 每次state/props,局部变量/函数/jsx都是新的 既然函数是新的,那么就会有一个问题,回调函数用…...
第一讲使用IDEA创建Java工程——HelloWorld
一、前言导读 为了能够让初学者更快上手Java,不会像其他书籍或者视频一样,介绍一大堆历史背景,默认大家已经知道Java这么编程语言了。本专栏只会讲解干货,直接从HelloWord入手,慢慢由浅入深,讲个各个知识点,这些知识点也是目前工作中项目使用的,而不是讲一些老的知识点…...
BootstrapBlazor组件使用:数据注解
文章目录 前言BB数据注解数据注解源码数据注解简介注解简单实例[BB 编辑弹窗](https://www.blazor.zone/edit-dialog)[ValidateForm 表单组件](https://www.blazor.zone/validate-form)使用简介 前言 BootstrapBlazor(一下简称BB)是个特别好用的组件,基本上满足了大…...
MySQL 触发器
文章目录 1.简介2.行级与语句级触发器3.触发时机4.触发器优缺点5.创建触发器语法示例 6.查看触发器7.删除触发器参考文献 1.简介 触发器(Trigger)是与表关联的命名数据库对象,当表发生特定事件时激活。 触发器的一些用途是对要插入表中的值执…...
DPDK主从进程模式 rte_mempool_put失败
版本:19.11.6 情景:主进程应用rte_mempool_create创建mempool,rte_mempool_get获取数据;从进程应用rte_mempool_put归还数据 问题:从进程rte_mempool_put无法归还数据 原因:DPDK通过rte_mempool_ops_tab…...
ZooKeeper 的工作原理
ZooKeeper 的工作原理可以概括为以下几个方面: 1. 数据模型 ZooKeeper 使用树形目录节点(znode)来建模关键的数据,每个 znode 可以存储数据内容,也可以作为目录包括子节点。客户端可以在节点上设置监听器。 2. 一致性算法 ZooKeeper 使用 ZAB(ZooKeeper Atomic Broadcast)协议…...
【业务功能篇73】分布式ID解决方案
业界实现方案 1. 基于UUID2. 基于DB数据库多种模式(自增主键、segment)3. 基于Redis4. 基于ZK、ETCD5. 基于SnowFlake6. 美团Leaf(DB-Segment、zkSnowFlake)7. 百度uid-generator() 1.基于UUID生成唯一ID UUID:UUID长度128bit,32个16进制字符,占用存储空…...
Qt安卓开发经验技巧总结V202308
01:01-05 pro中引入安卓拓展模块 QT androidextras 。pro中指定安卓打包目录 ANDROID_PACKAGE_SOURCE_DIR $$PWD/android 指定引入安卓特定目录比如程序图标、变量、颜色、java代码文件、jar库文件等。 AndroidManifest.xml 每个程序唯一的一个全局配置文件&…...
【vue2】前端实现下载后端返回的application/octet-stream文件流
1、下载csv/txt时 此时无须修改接口的响应格式 let filenameRegex /filename[^;\n]*((["]).*?\2|[^;\n]*)/; let matches filenameRegex.exec(data.headers[content-disposition]); let blob new Blob([\uFEFF data.data], {//目前只有csv格式type: text/csv;charse…...
【Java】SM2Utils(国密 SM2 工具类)
基于 bouncycastle 实现 国密 SM2 <!-- 引入 bouncycastle --> <dependency><groupId>org.bouncycastle</groupId><artifactId>bcprov-jdk15on</artifactId><version>1.70</version> </dependency>import lombok.Sneak…...
『C语言入门』初识C语言
文章目录 前言C语言简介一、Hello World!1.1 编写代码1.2 代码解释1.3 编译和运行1.4 结果 二、数据类型2.1 基本数据类型2.2 复合数据类型2.3 指针类型2.4 枚举类型 三、C语言基础3.1 变量和常量3.2 运算符3.3 控制流语句3.4 注释单行注释多行注释注释的作用 四、 …...
jira创建条目rest实用脚本
最近在搞crash崩溃分析,直接把解析到的信息录入jira系统进行跟踪; 经历了多次碰壁后终于调通,现记录一下 实用json请求脚本如下: {"fields":{"project":{"id":"10945"},"issuety…...
红外/可见光图像配准融合
红外/可见光图像配准融合 根据文献【1】,对于平行光轴的红外可见光双目配置进行图像配准,主要的限制是图像配准只是对特定的目标距离(Dtarget)有效。并排配置的配准误差 δx(以像素表示)的数学表达式为&…...
更高效稳定 | 基于ACM32 MCU的编程直流电源应用方案
随着电子设备的多样化发展,面对不同的应用场景,需要采用特定的供电电源。因此,在电子产品的开发测试过程中,必不可少使用编程直流电源来提供测试电压,协助完成初步的开发测试过程。 编程直流电源概述 编程直流电源结构…...
postgresql创建一个只读账户指定数据库
要在 PostgreSQL 中创建一个只读账户,您可以按照以下步骤进行操作: 1. **登录到 PostgreSQL:** 使用具有足够权限的管理员账户(通常是 "postgres" 用户)连接到 PostgreSQL 数据库。 2. **创建只读账户&…...
CSDN编程题-每日一练(2023-08-25)
CSDN编程题-每日一练(2023-08-25) 一、题目名称:影分身二、题目名称:小鱼的航程(改进版)三、题目名称:排查网络故障 一、题目名称:影分身 时间限制:1000ms内存限制:256M 题目描述&am…...
前端面试:【前端工程化】构建工具Webpack、Parcel和Rollup
嗨,亲爱的前端开发者!在现代Web开发中,前端工程化变得愈发重要。构建工具如Webpack、Parcel和Rollup帮助我们自动化任务、管理依赖、优化性能等。本文将深入探讨这三个前端构建工具,帮助你了解它们的优点和用途。 1. Webpack&…...
大型企业是否有必要进行数字化转型?
在数字化、信息化、智能化蓬勃发展的今天,初创公司可以很轻易的布局规划数字化发展的路径。而对于大型企业而言,其已经形成了较为成熟稳固的业务及组织架构,是否还有必要根据自身行业发展特点寻求数字化转型?(比如制造…...
05有监督学习——神经网络
线性模型 给定n维输入: x [ x 1 , x 1 , … , x n ] T x {[{x_1},{x_1}, \ldots ,{x_n}]^T} x[x1,x1,…,xn]T 线性模型有一个n维权重和一个标量偏差: w [ w 1 , w 1 , … , w n ] T , b w {[{w_1},{w_1}, \ldots ,{w_n}]^T},b w[w1,w1,…,wn]T,b 输…...
基于向量数据库的AI知识管理:开源工具如何实现知识处理效率提升300%
基于向量数据库的AI知识管理:开源工具如何实现知识处理效率提升300% 【免费下载链接】open-notebook An Open Source implementation of Notebook LM with more flexibility and features 项目地址: https://gitcode.com/GitHub_Trending/op/open-notebook 副…...
别再只会用滑动平均了!用Python从零实现数字陷波器,精准滤除50Hz工频干扰
从零构建Python数字陷波器:精准滤除50Hz工频干扰的工程实践 当你在深夜调试一个心爱的传感器项目时,突然发现采集到的数据波形上叠加了一个顽固的50Hz正弦波——这种经历想必不少硬件开发者都深有体会。工频干扰就像电子世界中的背景噪音,无…...
基于遗忘因子递推最小二乘法的电池模型参数在线辨识与优化
1. 电池模型参数辨识为什么需要FFRLS算法 我第一次接触电池参数辨识是在开发一款智能硬件时,当时发现传统最小二乘法有个致命问题——它会把所有历史数据同等对待。这就像用算盘计算平均数时,不管数据是昨天还是去年的,都按相同权重处理。但在…...
neural-style-tf视频风格转换实战:让整个视频充满艺术气息
neural-style-tf视频风格转换实战:让整个视频充满艺术气息 【免费下载链接】neural-style-tf TensorFlow (Python API) implementation of Neural Style 项目地址: https://gitcode.com/gh_mirrors/ne/neural-style-tf neural-style-tf是一个基于TensorFlow实…...
STM32F103R6数码管时钟实战:从Proteus仿真到按键调校全流程(附源码)
STM32F103R6数码管时钟实战:从Proteus仿真到按键调校全流程(附源码) 在嵌入式系统开发中,数码管显示是最基础也最实用的输出方式之一。本文将带您从零开始,基于STM32F103R6微控制器,构建一个完整的六位数码…...
SHA-3:从海绵结构到抗量子密码学的基石
1. SHA-3的诞生背景与核心价值 2004年,密码学界发现SHA-1存在理论漏洞,这直接推动了NIST启动新一代哈希算法竞赛。经过5年激烈角逐,Keccak团队提出的海绵结构方案最终胜出。与传统哈希算法不同,SHA-3不是对SHA-2的简单升级&#x…...
Simulink模型到AUTOSAR RTE的‘最后一公里’:手把手教你处理ARXML接口冲突并自动配置ISOLAR
Simulink模型到AUTOSAR RTE的‘最后一公里’:手把手教你处理ARXML接口冲突并自动配置ISOLAR 在汽车电子软件开发中,Simulink与AUTOSAR工具链的集成已经成为行业标配。但当你满怀期待地将Simulink模型导出为ARXML文件,准备导入ISOLAR进行后续开…...
STM32串口环形队列实现与优化
## 1. STM32串口环形队列实现方案### 1.1 环形队列数据结构设计环形队列(Ring Buffer)是嵌入式系统中处理串口数据流的经典方案,其核心数据结构定义如下:c #define RING_BUFF_SIZE 256 // 根据实际需求调整缓冲区大小typedef str…...
authentik:破解企业身份治理技术债的架构方案
authentik:破解企业身份治理技术债的架构方案 【免费下载链接】authentik The authentication glue you need. 项目地址: https://gitcode.com/GitHub_Trending/au/authentik 面对日益复杂的身份认证需求,技术决策者常常陷入两难:选择…...
Auto-Photoshop-StableDiffusion-Plugin:在Photoshop中无缝集成AI图像生成的技术实现方案
Auto-Photoshop-StableDiffusion-Plugin:在Photoshop中无缝集成AI图像生成的技术实现方案 【免费下载链接】Auto-Photoshop-StableDiffusion-Plugin A user-friendly plug-in that makes it easy to generate stable diffusion images inside Photoshop using eithe…...
