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

(分治算法3)leecode 53 最大子数组和(最大子段和)

题目描述

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

子数组是数组中的一个连续部分。

分治解法

这个问题可以分成从左半边数组找最大子段和从右半部分找最大子段和。
对于跨越两个数组的情况,我们可以从中间一定要包含左边界的数字或者右边界的数字,只需要一次遍历就可以了。

class Solution {public class Status {public int lSum, rSum, mSum, iSum;public Status(int lSum, int rSum, int mSum, int iSum) {this.lSum = lSum;this.rSum = rSum;this.mSum = mSum;this.iSum = iSum;}}public int maxSubArray(int[] nums) {return getInfo(nums, 0, nums.length - 1).mSum;}public Status getInfo(int[] a, int l, int r) {if (l == r) {return new Status(a[l], a[l], a[l], a[l]);}int m = (l + r) >> 1;Status lSub = getInfo(a, l, m);Status rSub = getInfo(a, m + 1, r);return pushUp(lSub, rSub);}public Status pushUp(Status l, Status r) {int iSum = l.iSum + r.iSum;int lSum = Math.max(l.lSum, l.iSum + r.lSum);int rSum = Math.max(r.rSum, r.iSum + l.rSum);int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);return new Status(lSum, rSum, mSum, iSum);}
}

相关文章:

(分治算法3)leecode 53 最大子数组和(最大子段和)

题目描述 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组中的一个连续部分。 分治解法 这个问题可以分成从左半边数组找最大子段和从右半部分找最大子段和…...

【C++】模板初级

【C】模板初级 泛型编程函数模板函数模板的概念函数模板格式函数模板的原理函数模板的实例化模板参数的匹配原则 类模板类模板格式类模板的实例化 泛型编程 当我们之前了解过函数重载后可以知道,一个程序可以出现同名函数,但参数类型不同。 //整型 voi…...

eslint 使用单引号,Prettier使用双引号冲突

当 ESLint 规则要求使用单引号 (quotes: single) 而 Prettier 默认使用双引号时,会发生配置冲突。为了解决这个问题,你需要统一这两个工具的配置,确保它们遵循相同的规则。这里推荐两种解决方案: 解决方案 1: 修改 ESLint 配置以…...

进化生物学的数学原理 知识点总结

1、进化论与自然选择 1.1 进化论 1、进化论 过度繁殖 -> 生存竞争 -> 遗传和变异 -> 适者生存 2、用进废退学说与自然选择理论 用进废退:一步适应:变异 适应 自然选择:两步适应:变异 选择 适应 3、木村资生的中性…...

如何挑到高质量的静态IP代理?

在数字化时代,静态住宅IP代理已成为网络活动中不可或缺的一部分。无论是数据采集、网站访问,还是其他需要隐藏真实IP地址的在线活动,高质量的静态住宅IP代理都发挥着至关重要的作用。今天IPIDEA代理IP将详细介绍如何获取高质量的静态住宅IP代…...

vagrant putty错误的解决

使用Vagrant projects for Oracle products and other examples 新创建的虚机,例如vagrant-projects/OracleLinux/8。 用vagrant ssh可以登录: $ vagrant ssh > vagrant: Getting Proxy Configuration from Host...Welcome to Oracle Linux Server …...

图像分割——U-Net论文介绍+代码(PyTorch)

0、概要 原理大致介绍了一下,后续会不断精进改的更加详细,然后就是代码可以对自己的数据集进行一个训练,还会不断完善,相应其他代码可以私信我。 一、论文内容总结 摘要:人们普遍认为,深度网络成功需要数…...

C#进阶-ASP.NET的WebService跨域CORS问题解决方案

在现代的Web应用程序开发中,跨域资源共享(Cross-Origin Resource Sharing, CORS)问题是开发者经常遇到的一个挑战。特别是当前端和后端服务部署在不同的域名或端口时,CORS问题就会显得尤为突出。在这篇博客中,我们将深…...

如何利用TikTok矩阵源码实现自动定时发布和高效多账号管理

在如今社交媒体的盛行下,TikTok已成为全球范围内最受欢迎的短视频平台之一。对于那些希望提高效率的内容创作者而言,手动发布和管理多个TikTok账号可能会是一项繁琐且耗时的任务。幸运的是,通过利用TikTok矩阵源码,我们可以实现自…...

Java高级编程技术详解:从多线程到算法优化的全面指南

复杂度与优化 复杂度与优化在算法中的应用 算法复杂度是衡量算法效率的重要指标。了解和优化算法复杂度对提升程序性能非常关键。本文将介绍时间复杂度和空间复杂度的基本概念,并探讨一些优化技术。 时间复杂度和空间复杂度 时间复杂度表示算法执行所需时间随输…...

Redis 分布式锁过期了,还没处理完怎么办?

为了防止死锁,我们会给分布式锁加一个过期时间,但是万一这个时间到了,我们业务逻辑还没处理完,怎么办? 这是一个分布式应用里很常见到的需求,关于这个问题,有经验的程序员会怎么处理呢&#xff…...

Vue2+Element-ui后台系统常用js方法

el-dialog弹框关闭清空form表单并清空验证 cancelDialog(diaLog, formRef) {this[diaLog] falseif (formRef) {this.$refs[formRef].resetFields()} }页面使用&#xff1a; <el-dialog :visible.sync"addSubsidyDialog.dialog" close"cancelDialog(addSub…...

Kafka高频面试题整理

文章目录 1、什么是Kafka?2、kafka基本概念3、工作流程4、Kafka的数据模型与消息存储机制1)索引文件2)数据文件 5、ACKS 机制6、生产者重试机制:7、kafka是pull还是push8、kafka高性能高吞吐的原因1&#xff09;磁盘顺序读写&#xff1a;保证了消息的堆积2&#xff09;零拷贝机…...

uniapp地图自定义文字和图标

这是我的结构&#xff1a; <map classmap id"map" :latitude"latitude" :longitude"longitude" markertap"handleMarkerClick" :show-location"true" :markers"covers" /> 记住别忘了在data中定义变量…...

k8s_探针专题

关于探针 生产环境中一定要给pod设置探针&#xff0c;不然pod内的应用发生异常时&#xff0c;K8s将不会重启pod。 需要遵循以下几个原则&#xff08;本人自己总结&#xff0c;仅供参考&#xff09;&#xff1a; 探针尽量简单&#xff0c;不要消耗过多资源。因为探针较为频繁的…...

MySQL触发器基本结构

1、修改分隔符符号 delimiter $$ 可以修改成$$ //都行 2、创建触发器函数名称 create trigger 函数名 3、什么样的操作出发&#xff0c;操作那个表 after&#xff1a;......之后触发 befor&#xff1a;......之前触发 insert&#xff1a;插入被触发 update&#xff1a;修改被触…...

前缀和(一维前缀和+二维前缀和)

前缀和 定义&#xff1a; 前缀和是指某序列的前n项和&#xff0c;可以把它理解为数学上的数列的前n项和&#xff0c;而差分可以看成前缀和的逆运算。合理的使用前缀和与差分&#xff0c;可以将某些复杂的问题简单化。 用途&#xff1a; 前缀和一般用于统计一个区间的和&…...

web前端五行属性:深入探索与实战解析

web前端五行属性&#xff1a;深入探索与实战解析 在Web前端开发中&#xff0c;五行属性这一概念或许听起来有些陌生。然而&#xff0c;如果我们将其与前端开发的核心理念相结合&#xff0c;就能发现其中蕴含的深刻内涵。本文将从四个方面、五个方面、六个方面和七个方面&#…...

白酒:茅台镇白酒的酒厂社会责任与可持续发展

云仓酒庄豪迈白酒&#xff0c;作为茅台镇的品牌&#xff0c;不仅在产品品质和口感方面有着卓着的表现&#xff0c;在酒厂社会责任和可持续发展方面也做出了积极的探索和实践。 首先&#xff0c;云仓酒庄豪迈白酒注重环境保护和资源利用。酒厂在生产过程中严格控制能源消耗和排放…...

音视频开发_SDL音频播放器的实现

今天向大家介绍一下如何通过 SDL 实现一个PCM音频播放器。这是一个最简单的播放器&#xff0c;它不涉及到音频的解复用&#xff0c;解码等工作。我们只需要将音频原始数据喂给 SDL 音频接口就可以听到悦耳的声音了。在下面的列子中我将向你演示&#xff0c;使用 SDL 做这样一个…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...