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 输…...
告别死记硬背!信息系统项目管理师(高项)思维导图活用法:从考前3个月到考前一天的全周期规划
信息系统项目管理师备考革命:用思维导图构建你的动态知识引擎 备考信息系统项目管理师(高项)的过程,常常让考生陷入两难困境:一方面要掌握庞杂的知识体系,另一方面又要应对实际工作中的时间压力。传统死记硬…...
ESP32S3端口死活不识别?别急着换线,先试试这个USB驱动修复大法
ESP32S3端口识别难题:从底层原理到实战修复的全方位指南 当你满怀期待地将ESP32S3开发板连接到电脑,准备开始物联网项目的开发时,却发现设备管理器里怎么也找不到对应的COM端口——这种挫败感我深有体会。作为一款功能强大的Wi-Fi/蓝牙双模芯…...
Mac Mouse Fix革命性指南:让普通鼠标在Mac上实现专业级操作体验
Mac Mouse Fix革命性指南:让普通鼠标在Mac上实现专业级操作体验 【免费下载链接】mac-mouse-fix Mac Mouse Fix - A simple way to make your mouse better. 项目地址: https://gitcode.com/GitHub_Trending/ma/mac-mouse-fix Mac Mouse Fix是一款专为Mac用户…...
可视化是对比原始数据和填补数据的强大工具。你可以使用箱线图、密度图或散点图来可视化原始数据和填补后的数据
下面的内容摘录自《用R探索医药数据科学》专栏文章的部分内容(原文5665字)。 2篇2章6节:R的多重填补法中随机回归填补法的应用,MICE包的实际应用和统计与可视化评估-CSDN博客 在数据分析中,缺失数据是常见且具有挑战性…...
为什么你的LoRA微调总在step 217崩溃?Python大模型调试日志解密:从`torch._C._debug_dump_tracing_state()`到生产级可观测性
第一章:LoRA微调崩溃现象的系统性认知LoRA(Low-Rank Adaptation)作为一种高效参数微调技术,虽显著降低显存开销与训练成本,但在实际落地过程中频繁出现训练过程突然中断、梯度爆炸、loss突变为NaN或GPU内存溢出等“崩溃…...
别再让Bug溜走!手把手教你用SVA在UVM里给芯片验证加个“监控探头”
芯片验证工程师的"电子眼":用SVA在UVM中构建智能监控体系 想象一下,你正在负责一个复杂SoC芯片的验证工作。随着设计规模不断扩大,传统的测试方法就像在黑暗的房间里寻找掉落的针——效率低下且容易遗漏关键问题。这时,…...
Excel中利用VBA批量检测URL链接状态
1. 为什么需要批量检测URL链接状态 在日常工作中,我们经常会遇到需要处理大量URL链接的情况。比如做数据分析时收集的网站列表、电商平台的商品链接、或者是内容管理系统中的文章地址。这些链接中难免会有失效的情况,可能是网站改版、页面删除࿰…...
如何用Video2X实现视频画质智能增强?零基础入门到精通指南
如何用Video2X实现视频画质智能增强?零基础入门到精通指南 【免费下载链接】video2x A lossless video/GIF/image upscaler achieved with waifu2x, Anime4K, SRMD and RealSR. Started in Hack the Valley II, 2018. 项目地址: https://gitcode.com/GitHub_Trend…...
从合合技术揭秘到自建数据集:手把手训练你的文档矫正模型
从合合技术揭秘到自建数据集:手把手训练你的文档矫正模型 在数字化办公场景中,文档图像矫正技术正成为提升OCR识别精度的关键环节。当开发者面对弯曲、折叠或透视变形的文档时,传统参数化方法往往难以应对复杂形变,而基于深度学习…...
数字记忆策展:WeChatMsg与数据主权时代的个人记忆管理
数字记忆策展:WeChatMsg与数据主权时代的个人记忆管理 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeCha…...
