当前位置：首页 > news >正文

数据结构与算法之动态规划: LeetCode 53. 最大子数组和 (Ts版)

news 来源：原创 2025/7/18 16:19:43

最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/

描述

给你一个整数数组 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 <= $10^5$
- $10^4$ <= nums[i] <= $10^4$
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解

Typescript 版算法实现

1 ) 方案1: 动态规划

function maxSubArray(nums: number[]): number {let pre = 0, maxAns = nums[0];nums.forEach((x) => {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);});return maxAns;
};

2 ）方案2: 动态规划

function maxSubArray(nums: number[]): number {const len = nums.length;if (len === 0) return 0;// dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和let dp = new Array(len);dp[0] = nums[0];let res = dp[0];for (let i = 1; i < len; i++) {dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];res = Math.max(res, dp[i]);}return res;
}

3 ）方案3: 分治

// 定义 Status 接口
interface IStatus {lSum: number;rSum: number;mSum: number;iSum: number;
}function Status(l:number, r:number, m:number, i:number) {this.lSum = l;this.rSum = r;this.mSum = m;this.iSum = i;
}function pushUp(l:IStatus, r:IStatus) {const iSum = l.iSum + r.iSum;const lSum = Math.max(l.lSum, l.iSum + r.lSum);const rSum = Math.max(r.rSum, r.iSum + l.rSum);const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);return new Status(lSum, rSum, mSum, iSum);
}function getInfo (a:number[], l:number, r:number) {if (l === r) return new Status(a[l], a[l], a[l], a[l]);const m = (l + r) >> 1;const lSub = getInfo(a, l, m);const rSub = getInfo(a, m + 1, r);return pushUp(lSub, rSub);
}function maxSubArray(nums: number[]): number {return getInfo(nums, 0, nums.length - 1).mSum;
}

数据结构与算法之动态规划: LeetCode 53. 最大子数组和 (Ts版)

最大子数组和 https://leetcode.cn/problems/maximum-subarray/description/ 描述给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和子数组是数组中的一个连续部分示例 1 …...

编程日记 2025/7/18 16:19:43

活动预告 | Microsoft Azure 在线技术公开课：使用 Azure OpenAI 服务构建生成式应用

课程介绍通过 Microsoft Learn 免费参加 Microsoft Azure 在线技术公开课，掌握创造新机遇所需的技能，加快对 Microsoft Cloud 技术的了解。参加我们举办的“使用 Azure OpenAI 服务构建生成式应用”活动，了解如何使用包括 GPT 在内的强大的…...

编程日记 2025/7/18 15:58:08

Python爬虫（二）- Requests 高级使用教程

文章目录前言一、Session 对象1. 简介2. 跨请求保持 Cookie3. 设置缺省数据4. 方法级别参数不被跨请求保持5. 会话作为上下文管理器6. 移除字典参数中的值二、请求与响应1. 请求与响应对象1.1 获取响应头信息1.2 获取发送到服务器的请求头信息三、SSL 证书验证1. 忽略 SSL 证…...

编程日记 2025/7/14 15:56:03

协议幻变者：DeviceNet转ModbusTCP网关开启机器手臂智能新纪元

技术背景DeviceNet是一种广泛应用于工业自动化领域的现场总线标准，它能够实现控制器与现场设备之间的高效通信，常用于连接各种传感器、执行器以及其他工业设备，如机器人、电机驱动器等，具有实时性强、可靠性高的特点。而ModbusTCP…...

编程日记 2025/7/16 17:30:07

package cn.ziqirj.common.utils;import lombok.Getter; import lombok.Setter;import java.util.ArrayList; import java.util.List;/*** 模拟Map集合，key不可重复，按插入顺序排序* author zhangji** param <T>*/ public class CustomOrderlyMap&…...

编程日记 2025/6/30 22:10:31

CA系统的设计(CA证书生成，吊销，数字签名生成）

CA系统概述 CA认证系统是一种基于公钥密码基础设施（PKI）的信息安全技术，它可以为网络通信双方提供身份认证、数据加密、数字签名等功能。CA认证系统的核心是证书授权机构（CA），它负责为用户（节点…...

编程日记 2025/7/13 1:16:37

流计算需要框架吗？SPL 可能是更好的选择

流数据源通常是动态、无界的，看起来与静态、有限的批数据源区别较大，传统的数据库技术在架构上难以直接处理流数据源，只能让位于后来者。heron\samza\storm\spark\flink等计算框架最先完成突破，在流计算技术中占得先发优势。这些框…...

编程日记 2025/7/13 7:20:50

Vue-Router之嵌套路由

在路由配置中，配置children import Vue from vue import VueRouter from vue-routerVue.use(VueRouter)const router new VueRouter({mode: history,base: import.meta.env.BASE_URL,routes: [{path: /,redirect: /home},{path: /home,name: home,component: () &…...

编程日记 2025/7/18 8:04:29

MySQL 读写分离

MySQL 读写分离一、配置主库(Master) 1.修改主库的配置文件修改主库的 my.cnf 配置文件，生成二进制日志 (binary log) 和服务器唯一ID，这是实现主从复制的必要配置 [mysqld] # skip-grant-tables userroot port3306 basedir/usr/local/mysql datad…...

编程日记 2025/7/16 5:18:06

记一次音频无输出的解决方案

啊啊啊，刷个抖音就发现个死电脑死都不出声，捣鼓了一天才解决打开wav文件时，提示错误找不到音频播放设备 0xc00d36fa 起初以为是声卡坏了，就到官网下载、更新了声卡驱动。无用什么驱动精灵也检测了，但也测不出啥来。…...

编程日记 2025/7/14 19:52:35

3D数学基础2

矩阵的行列式在任意方阵中都存在至少一个标量，称作该方阵的行列式。在线性代数中，行列式有很多有用的性质线性运算法则方阵 M M M的行列式记作 ∣ M ∣ |M| ∣M∣或“det M”。非方阵矩阵的行列式是未定义的。注意，在书写行列式时&…...

编程日记 2025/7/18 5:15:08

Java开发生态2024年度总结报告

1 关键要点尽管数据显示 Java 17 是最常用 JDK，但其用户占比并未超过半数。根据 New Relic 2024 Java 生态系统状态报告，Java 17、11 和 8 的用户比例分别为 35%、33% 和 29%。New Relic 数据中所谓“快速采用”指 Java 21 的采用率仅为 1.4%。虽相较 J…...

编程日记 2025/7/17 10:04:34

1月第三讲：Java子线程无法获取Attributes的解决方法

在Java多线程编程中，开发者经常会遇到子线程无法获取主线程设置的Attributes的问题。Attributes通常用于存储与当前线程相关的数据，尤其在Web应用中，它们常用于请求上下文的管理。然而，由于Java线程是独立运行的，每个线…...

编程日记 2025/7/16 18:44:43

更新金碟云星空单据供应商和币别

--应付单 select FSUPPLIERID from [dbo].[T_AP_PAYABLE] where FBILLNO=AP2024121670 select FSUPPLIERID,FCURRENCYID,* from [dbo].[T_AP_PAYABLE] where FBILLNO=AP2024121670 -- update T_AP_PAYABLE set FSUPPLIERID=100567 where FBILLNO=AP2024121670 -- update T_…...

编程日记 2025/7/15 14:59:49

from memory cache 修复记录

背景浏览器的页签图标，不想要了改代码：设置浏览器页签的代码本地环境测试，没有问题，一次性修改成功于是打包，部署到测试环境，然而，还是有接下的解决方法： 1、清除浏览器缓…...

编程日记 2025/7/17 13:28:55

spring入门程序

安装eclipse https://blog.csdn.net/qq_36437991/article/details/131644570 新建maven项目安装依赖包 pom.xml <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation&quo…...

编程日记 2025/7/16 20:50:02

用于实现无缝滚动效果的vue-seamless-scroll插件

它通常用于在网页或应用中实现内容的自动滚动效果，如新闻公告、图片轮播等，支持横向和纵向滚动，并且可以自定义滚动速度、方向等参数，适合展示一些需要持续循环展示的信息。在Vue2项目中使用vue-seamless-scroll插件的步骤如下&…...

编程日记 2025/7/14 10:35:09

借助 FinClip 跨端技术探索鸿蒙原生应用开发之旅

在当今数字化浪潮汹涌澎湃的时代，移动应用开发领域正经历着深刻的变革与创新。鸿蒙操作系统的崛起，以其独特的分布式架构和强大的性能表现，吸引了众多开发者的目光。而FinClip 跨端技术的出现，为开发者涉足鸿蒙原生应用开发提供了…...

编程日记 2025/7/13 1:36:05

【机器学习】机器学习的基本分类-自监督学习-对比学习（Contrastive Learning）

对比学习是一种自监督学习方法，其目标是学习数据的表征（representation），使得在表征空间中，相似的样本距离更近，不相似的样本距离更远。通过设计对比损失函数（Contrastive Loss）&…...

编程日记 2025/7/13 18:25:50

python之eval函数

功能：将字符串str当成有效的表达式来求值并返回计算结果语法：eval(source,[,globals[,locals]])->value 参数： source：一个python表达式或函数compile()返回的代码对象globals：可选。必须是dictionarylocals&am…...

编程日记 2025/7/12 19:23:10

NXP i.MX8系列平台开发讲解 - 5.3 调试篇(二) - 掌握Dynamic debug调试

专栏文章目录传送门：返回专栏目录 Hi, 我是你们的老朋友，主要专注于嵌入式软件开发，有兴趣不要忘记点击关注【码思途远】文章目录目录掌握Dynamic debug调试 1. 认识Dynamic debug 2. 内核配置 3. 使用Dynamic debug 3.1 查看当前的…...

编程日记 2025/7/16 5:00:08

QT----------常用界面组件的使用

一、QComboBox 类主要功能：提供一个下拉列表，用户可以从中选择一个或多个选项。 #include <QApplication> #include <QComboBox> #include <QVBoxLayout> #include <QWidget> #include <QMessageBox>int main(int argc…...

编程日记 2025/7/17 7:51:54

重新整理机器学习和神经网络框架

本篇重新梳理了人工智能（AI）、机器学习（ML）、神经网络（NN）和深度学习（DL）之间存在一定的包含关系，以下是它们的关系及各自内容,以及人工智能领域中深度学习分支对比整理。…...

编程日记 2025/7/15 19:36:22

AJAX详解

AJAX是前后端交互的重要工具结合前后端交互基础理解：前后端交互详解(建议收藏)-CSDN博客 1. AJAX - 到底什么是Ajax? ajax 全名 async javascript and XML(异步JavaScript和XML)，是一种用于向服务器异步发送 HTTP 请求并接收响应的技术。 XML 指可扩…...

编程日记 2025/7/17 6:27:27

golang中的异常处理机制

今天是2024最后一天，祝大家新年梦想成真，继续我的魅力golang，昨天发的错误处理，是明显的可预见、可恢复的问题，然而，不可预见的问题，往往更多，golang也有自己的一套，完全…...

编程日记 2025/7/16 21:49:53

HTML5 开关（Toggle Switch）详细讲解

HTML5 开关（Toggle Switch）详细讲解 1. 任务概述开关（Toggle Switch）是一种用于表示二元状态（如开/关）的用户界面控件。用户可以通过点击开关来切换状态，常见于设置选项、开关功能等场景。 2…...

编程日记 2025/7/14 1:43:17

【前端】Node.js使用教程

目录一、?Node.js开发环境和编译 1.1 安装Node.js 1.2 创建一个Node.js项目 1.3 编写Node.js程序 1.4 运行Node.js程序 1.5 使用Node.js模块二、高级的Node.js编程概念和示例 2.1 异步编程 2.2 错误处理 2.3 网络请求 2.4 构建Web服务器 2.5 数据库交互三、No…...

编程日记 2025/7/14 21:56:24

在CodeBlocks搭建SDL2工程构建TFT彩屏模拟器虚拟TFT彩屏幕显示

在CodeBlocks搭建SDL2工程构建TFT彩屏模拟器虚拟TFT彩屏幕显示参考文章源码下载地址一、SDL2的创建、初始化、退出二、系统基本Tick、彩屏刷新、按键事件三、彩屏获取与设置颜色四、彩屏填充颜色及清屏五、彩屏显示中文和英文字符串六、彩屏显示数字七、彩屏初始化八、主函数测…...

编程日记 2025/7/18 11:17:04

BurstAttention：高效的分布式注意力计算框架

BurstAttention：高效的分布式注意力计算框架在现代大型语言模型（LLMs）的应用中，提升注意力机制的计算效率已成为研究的热点。当前，提升计算效率主要有两种方法：一种是优化单设备的计算和存储能力&#xf…...

编程日记 2025/7/14 18:34:26

sentinel集成nacos启动报[check-update] get changed dataId error, code: 403错误排查及解决

整合nacos报403错误因为平台写的一个限流代码逻辑有问题，所以准备使用sentinel来限流。平台依赖里面已经引入了，之前也测试过，把sentinel关于nacos的配置加上后，启动一直输出403错误 [fixed-10.0.20.188_8848-test] [check-upda…...

编程日记 2025/7/16 1:35:16

[TOTP]android kotlin实现 totp身份验证器类似Google身份验证器

背景：自己或者公司用一些谷歌身份验证器或者microsoft身份验证器，下载来源不明，或者有广告，使用不安全。于是自己写一个，安全放心使用。代码已开源：shixiaotian/sxt-android-totp: android totp authenti…...

编程日记 2025/7/17 14:00:57

IDEA+Docker一键部署项目SpringBoot项目

文章目录 1. 部署项目的传统方式2. 前置工作3. SSH配置4. 连接Docker守护进程5. 创建简单的SpringBoot应用程序6. 编写Dockerfile文件7. 配置远程部署 7.1 创建配置7.2 绑定端口7.3 添加执行前要运行的任务 8. 部署项目9. 开放防火墙的 11020 端口10. 访问项目11. 可能遇到的问…...

编程日记 2025/7/13 14:46:35

【发票提取明细+发票号改名】批量提取PDF电子发票明细导出Excel表格并改名技术难点，批量PDF多区域内容识别提取明细并用内容改名的小结

1、图片版的发票提取表格改名【批量图片发票识别表格】批量图片发票的提取Excel表格和提取字段改名，扫描发票识别表格，拍照发票识别表格，图片发票识别改名我们在工作中很多扫描发票，拍照发票，需要整理成excel表格&am…...

编程日记 2025/7/18 1:31:15

pyQT + OpenCV相关练习

一、设计思路 1、思路分析与设计本段代码是一个使用 PyQt6 和 OpenCV 创建的图像处理应用程序。其主要功能是通过一个图形界面让用户对图片进行基本的图像处理操作，如灰度化、翻转、旋转、亮度与对比度调整，以及一些滤镜效果（模糊、锐化、边…...

编程日记 2025/7/14 12:37:21

石岩路边理发好去处

周末带娃去罗租公园玩，罗租公园旁边就是百佳华和如意豪庭小区，发现如意豪庭小区对面挺多路边理发摊点理发摊点聚焦在这里的原因是刚好前面城管来了暂时避避，例如还有一个阿姨剪到一半就跟着过来。这里的城管只是拍了一处没有摊位的地方&…...

编程日记 2025/7/18 10:00:22

音视频入门基础：MPEG2-PS专题（2）——使用FFmpeg命令生成ps文件

一、错误的命令通过FFmpeg命令可以将mp4文件转换为ps文件，PS文件中包含PS流数据。由于PS流/PS文件对应的FFInputFormat结构为： const FFInputFormat ff_mpegps_demuxer {.p.name "mpeg",.p.long_name NULL_IF_CONFIG_SMALL…...

编程日记 2025/7/14 4:40:21

整合版canal ha搭建--基于1.1.4版本

开启MySql Binlog（1）修改MySql配置文件（2）重启MySql服务,查看配置是否生效（3）配置起效果后，创建canal用户，并赋予权限安装canal-admin（1）解压 canal.admin-1…...

编程日记 2025/7/17 18:26:22

[python SQLAlchemy数据库操作入门]-15.联合查询，跨表获取股票数据

哈喽，大家好，我是木头左！在开始探讨如何利用SQLAlchemy实现复杂的联合查询之前，首先需要深入理解其核心组件——对象关系映射（ORM）。ORM允许开发者使用Python类来表示数据库中的表，从而以一种更直观、面向对象的方式来操作数据库。 SQLAlchemy中的JOIN操作详解在SQLA…...

编程日记 2025/7/17 22:30:22

PTA数据结构作业一

6-1 链表的插入算法本题要求实现一个插入函数，实现在链表llist中的元素x之后插入一个元素y的操作。函数接口定义： int InsertPost_link(LinkList llist, DataType x, DataType y); 其中 llist是操作的链表，x是待插入元素y的前驱节点元素…...

编程日记 2025/7/12 15:43:57

前端（九）js介绍(2)

js介绍(2) 文章目录 js介绍(2)一、函数1.1函数的两种形式1.2函数的作用域1.3声明与提升二、bom操作三、dom操作一、函数 1.1函数的两种形式 //有参函数 //js中的函数只能返回一个值，如果要返回多个需要放在数组或对象中 function func(a,b){return ab } func(1,…...

编程日记 2025/7/15 5:10:58

CUTLASS：高性能 CUDA 线性代数模板库详解

CUTLASS：高性能 CUDA 线性代数模板库详解引言什么是 CUTLASS？CUTLASS 的主要特点： CUTLASS 的用途如何安装 CUTLASS1. 环境准备2. 下载 CUTLASS3. 构建 CUTLASS4. 设置环境变量5. 验证安装使用 CUTLASSCUTLASS 的优势总结引言在深度学习…...

编程日记 2025/7/14 10:53:30

关于CISP报名费用详情

CISP即“注册信息安全专业人员”，是中国信息安全测评中心实施的国家认证项目，旨在培养信息安全领域的专业人才。对于有意报考CISP的考生而言，了解报名考试费用是备考过程中不可或缺的一环。 CISP的报名考试费用主要包括培训费用、考试费用、…...

编程日记 2025/7/15 20:06:27

css 关于flex布局中子元素的属性flex

css flex布局中子元素的属性flex 1. flex 是 flex-grow、flex-shrink 和 flex-basis 的简写语法格式： flex: [flex-grow] [flex-shrink] [flex-basis];各属性解析： flex-grow: 子元素如何按比例分配父元素的剩余空间。默认值：0&#…...

编程日记 2025/7/13 20:28:22

功率器件热设计基础（四）——功率半导体芯片温度和测试方法

/ 前言 / 功率半导体热设计是实现IGBT、碳化硅SiC高功率密度的基础，只有掌握功率半导体的热设计基础知识，才能完成精确热设计，提高功率器件的利用率，降低系统成本，并保证系统的可靠性。功率器件热设计基础系列文章会…...

编程日记 2025/7/13 18:56:03

OpenStack系列第四篇：云平台基础功能与操作（Dashboard）

文章目录 1. 镜像（Image）添加镜像查看镜像删除镜像 2. 卷（Volume）创建卷查看卷删除卷 3. 网络（虚拟网络）创建网络查看网络删除网络 4. 实例类型创建实例类型查看实例类型删除实例类型 4. 密钥对&#xff08…...

编程日记 2025/7/14 5:28:30

WebSocket封装

提示：记录工作中遇到的需求及解决办法文章目录前言二、背景三、WebSocket3.1 什么是 WebSocket ？为什么使用他？四、封装 WebSocket4.1 Javascript 版本4.2 Typescript 版本4.3 如何使用？五、我的痛点如何处理前言本文将介绍 WebSocket 的封装，比如：心跳机制，重连和一…...

编程日记 2025/7/14 18:53:16