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

【LeetCode】每日一题:最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。

解题思路

要注意最小值是整个前缀,主要是cumsum然后按照买卖股票的思路做的,但是边界处理很容易错,可以以最开始几个边界来判定初始值,这个方法挺好用的。

AC代码

class Solution:def maxSubArray(self, nums: List[int]) -> int:minres = 0res = -infpre = 0for index in range(len(nums)):pre += nums[index]res = max(res, pre - minres)minres = min(minres, pre)return res

官方思路

动态规划

注意动态规划的重点是以i结尾的最大子串,只有加上结尾这个条件才能写递归式。

我们需要两个变量,一个变量用来记录上一个递归结果,其应该为单独上一个数或者上一个数加上前面一段。这里的变量逻辑和cumsum的前缀和逻辑是有区别的。

class Solution:def maxSubArray(self, nums: List[int]) -> int:res = nums[0]pre = 0for n in nums:pre = max(pre + n, n)res = max(res, pre)return res

二分法

线段树的思想,第一次看到,需要维护四个变量,分辨是非左端点最大值,有点点最大值,整区间值和区间内最大值,这个思路其实像是多道二分法题目的合并了,这种做法的好处在于可以存储任意区间的结果。如果需要多次输出结果,这种方法的优势就比较明显了。

class Solution {
public:struct Status {int lSum, rSum, mSum, iSum;};Status pushUp(Status l, Status r) {int iSum = l.iSum + r.iSum;int lSum = max(l.lSum, l.iSum + r.lSum);int rSum = max(r.rSum, r.iSum + l.rSum);int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);return (Status) {lSum, rSum, mSum, iSum};};Status get(vector<int> &a, int l, int r) {if (l == r) {return (Status) {a[l], a[l], a[l], a[l]};}int m = (l + r) >> 1;Status lSub = get(a, l, m);Status rSub = get(a, m + 1, r);return pushUp(lSub, rSub);}int maxSubArray(vector<int>& nums) {return get(nums, 0, nums.size() - 1).mSum;}
};

相关文章:

【LeetCode】每日一题:最大子数组和

给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组是数组中的一个连续部分。 解题思路 要注意最小值是整个前缀&#xff0c;主要是cumsum然后按照买卖股票的思路做的&a…...

什么是进程?

前言&#x1f440;~ 上一章我们介绍了计算机组成的入门知识&#xff0c;了解这些之后&#xff0c;今天来聊聊进程 进程 PCB pcb中的常见属性 进程调度 进程的状态 进程的优先级 上下文 记账信息 虚拟地址空间 如果各位对文章的内容感兴趣的话&#xff0c;请点点小赞&a…...

后端返回base64文件流下载

后端返回base64文件流: 前端处理&#xff1a; downloadTemplate () {this.$API.downloadTemplate().then(({ data }) > {const binaryString atob(data) // 解码base64字符串const byteArray new Uint8Array(binaryString.length) // 创建一个Uint8Arrayfor (let i 0; i…...

云原生面试

云原生面试 Kubernetes原理Kubernetes 如何保证集群的安全性。简述 Kubernetes 准入机制简述Kubernetes Secret 有哪些使用方式简述Kubernetes PodSecurityPolicy机制简述Kubernetes PodSecurityPolicy机制能实现哪些安全策略简述Kubernetes 网络策略原理简述Kubernetes 数据持…...

深度学习入门2—— 神经网络的组成和3层神经网络的实现

由上一章结尾&#xff0c;我们知道神经网络的一个重要性质是它可以自动地从数据中学习到合适的权重参数。接下来会介绍神经网络的概要&#xff0c;然后再结合手写数字识别案例进行介绍。 1.神经网络概要 1.1从感知机到神经网 我们可以用图来表示神经网络&#xff0c;我们把最…...

tensorflow学习:错误 InternalError: Dst tensor is not initialized

tensorflow学习&#xff1a;错误 InternalError: Dst tensor is not initialized_dst tensor is not initialized.-CSDN博客https://blog.csdn.net/wanglitao588/article/details/77033659...

Docker环境安装anythingllm

拉镜像 docker pull mintplexlabs/anythingllm建目录 export STORAGE_LOCATION$HOME/anythingllm && \ mkdir -p $STORAGE_LOCATION && \ touch "$STORAGE_LOCATION/.env"检查目录具有写权限 # 为目录anythingllm赋写权限 chmod 777 anythingllm 启…...

FEC 向前纠错编码

随写&#xff0c;看的有点杂&#xff0c;简单记一下。 应该叫ReedSolomon FEC RS算法简单来讲就是&#xff0c;根据已有数据&#xff0c;构造模型&#xff0c;然后根据模型判纠错&#xff1f; 简单来讲&#xff0c;两点确定一条直线&#xff0c;直线直线上的点都会满足 y kx…...

【jupyter notebook】解决打不开以及安装扩展插件的问题

文章目录 问题描述问题 1解决问题 2解决 问题描述 问题 1 在自定义的虚拟环境下&#xff0c;安装 jupyter notebook 6.4.12 版本时&#xff0c;报以下错误&#xff1a; 解决 查了一些 解决方法&#xff0c;执行以下命令即可解决&#xff1a; conda install traitlets5.9.0 …...

Perl文件句柄深度解析:掌握文件操作的核心

Perl中的文件句柄是进行文件输入输出操作的关键。它们提供了一种机制&#xff0c;允许Perl脚本打开文件、读写数据、定位文件指针&#xff0c;以及关闭文件。理解文件句柄的使用对于编写高效的Perl脚本至关重要。本文将深入探讨Perl文件句柄的概念、使用方法和最佳实践。 1. 文…...

Tomcat 下载部署到 idea

一、下载Tomcat Tomcat 是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个核心项目&#xff0c;免费开源、并支持Servlet 和JSP 规范。属于轻量级应用服务器&#xff0c;在中小型系统和并发访问用户不是很多的场合下被普遍使用&#xff0c;是开发…...

FutureTask如何使用?

FutureTask是Java中的一个具体类&#xff0c;它实现了RunnableFuture接口&#xff0c;该接口结合了Runnable和Future的功能。FutureTask可以用于表示一个可以取消的异步计算。FutureTask非常适合用于与Executor框架一起使用&#xff0c;但也可以单独使用。 FutureTask的基本用…...

Webpack: 如何借助预处理器、PostCSS 等构建现代 CSS 工程环境

概述 在开发 Web 应用时&#xff0c;我们通常需要编写大量 JavaScript 代码 —— 用于控制页面逻辑&#xff1b;编写大量 CSS 代码 —— 用于调整页面呈现形式。问题在于&#xff0c;CSS 语言在过去若干年中一直在追求样式表现力方面的提升&#xff0c;工程化能力薄弱&#xff…...

一篇文章告诉你如何正确使用chatgpt提示词

在chatgpt大火的时候&#xff0c;出现了一波学习chatgpt提示词的热潮&#xff0c;互联网出现很多了使用的学习提示词的课程。其中我觉得斯坦福大学教授吴恩达博士推出prompt engineer课最全面。接下来总结他课程中正确使用提示词工程的方法。 1. 明确目标 明确你希望ChatGPT完…...

qt基于QGraphicsView的屏幕旋转

一、代码实现 实现代码示例 MainWindow2 w;QGraphicsScene *scene new QGraphicsScene;QGraphicsProxyWidget *gw scene->addWidget(&w);// 旋转角度gw->setRotation(90);QGraphicsView *view new QGraphicsView(scene);//view->resize(1024, 600);//scene-&g…...

一个土木工程专业背景的开发者,讲述开源带给他的力量

在前段时间我们举办的“TDengine Open Day”第一季技术沙龙中&#xff0c;TDengine 应用研发高级工程师谭雪峰进行的“开源之路&#xff1a;程序员的成长与探索”主题分享获得了众多参会者的好评。谭雪峰从自身独特的职业发展经历出发&#xff0c;分享了自己在开源领域的种种收…...

express+vue在线im实现【四】

往期内容 expressvue在线im实现【一】 expressvue在线im实现【二】 expressvue在线im实现【三】 本期示例 本期总结 支持了音频的录制和发送&#xff0c;如果觉得对你有用&#xff0c;还请点个免费的收藏与关注 下期安排 在线语音 具体实现 <template><kl-dial…...

【Qt 实现3D按钮】

要在Qt中实现3D按钮&#xff0c;你可以使用QML和Qt 3D模块。这是一个简单的例子&#xff0c;展示了如何在Qt中创建一个3D按钮&#xff1a; 首先&#xff0c;确保你的系统中已经安装了Qt 3D模块。在命令行中输入以下命令检查&#xff1a; qmlscene --version如果没有安装&…...

8.每日LeetCode-笔试题,交替打印数字和字母

代码地址&#xff1a;interview-go: Go高级面试总结 问题描述 ​​​交替打印数字和字母 使用两个 goroutine 交替打印序列&#xff0c;一个 goroutine 打印数字&#xff0c; 另外一个 goroutine 打印字母&#xff0c; 最终效果如下&#xff1a; 12AB34CD56EF78GH910IJ1112KL…...

UE5近战对抗系统Tutorial

文章目录 BP_Character 组合攻击Notify State 检测攻击BP_Character 攻击反馈BP_Character 生命系统BP_Character 死亡效果BP_Character 武器系统BP_Enemy 初始化和行为树 BP_Character 组合攻击 首先我们获取攻击动画&#xff0c;在这里使用的是 Easy Combo Buffering 的攻击…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...