LeetCode 面试题 16.17. 连续数列
文章目录
- 一、题目
- 二、C# 题解
一、题目
给定一个整数数组,找出总和最大的连续数列,并返回总和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
- 如果你已经实现复杂度为
O(n)的解法,尝试使用更为精妙的分治法求解。
点击此处跳转题目。
二、C# 题解
使用动态规划可以实现 O(n) 的复杂度。使用 max 记录以 j 结尾的最大连续和,其递推关系为:
m a x [ j ] = M A X { m a x [ j − 1 ] + n u m s [ j ] , n u m s [ j ] > 0 m a x [ j − 1 ] , n u m s [ j ] ≤ 0 n u m s [ j ] , m a x [ j − 1 ] < 0 max[j]= MAX\left\{ \begin{array}{l l} max[j-1]+nums[j],&nums[j]>0\\ max[j-1],&nums[j]\leq0\\ nums[j],&max[j-1]<0 \end{array} \right. max[j]=MAX⎩ ⎨ ⎧max[j−1]+nums[j],max[j−1],nums[j],nums[j]>0nums[j]≤0max[j−1]<0
每次纳入 nums[j] 并考虑:
max < 0,则直接从 j 开始就好,即设置max = 0。因为算上前面的序列,和只会更小。max += nums[j],与ans比较,ans结果取最大值。
理论上需要开辟一个 O(n) 数组存储 max,但是由于只需要求 max 的最大值 ans,因此可以边计算边更新 ans,省去了 O(n) 的空间。
public class Solution {public int MaxSubArray(int[] nums) {int ans = nums[0], max = ans;for (var j = 1; j < nums.Length; j++) {if (max < 0) max = 0; // 先前的序列如果 < 0,则直接抛弃,从第 j 位开始重新计数max += nums[j]; // 并入第 j 位if (max > ans) ans = max; // 更新结果}return ans;}
}
- 时间:84 ms,击败 61.11% 使用 C# 的用户
- 内存:38.23 MB,击败 77.78% 使用 C# 的用户
使用分治可以实现 O(logn) 的复杂度。将数组 nums 一分为二,记为 left 和 right。则 nums 的答案 Max 可能有如下 3 中情况:
- 在 left 中。

- 在 right 中。

- 在 left 和 right 交界处。

因此,需要记录区间的左端最大连续和 LMax(红色) 与右端最大连续和 RMax(黄色),其对应的更新情况如下:
- LMax:

- RMax:

同时,使用 Sum(绿色)记录区间的总长度。
public class Solution {public struct Range{public int LMax; // 从左端开始的最长连续和public int RMax; // 以右端结尾的最长连续和public int Sum; // 区间总和public int Max; // 区间内最长连续和public Range(int l, int r, int s, int m) {LMax = l;RMax = r;Sum = s;Max = m;}public static Range operator +(Range left, Range right) {int lMax = Math.Max(left.LMax, left.Sum + right.LMax);int rMax = Math.Max(right.RMax, left.RMax + right.Sum);int sum = left.Sum + right.Sum;int max = Math.Max(Math.Max(left.Max, right.Max), left.RMax + right.LMax);return new Range(lMax, rMax, sum, max);}}public int MaxSubArray(int[] nums) {return Partition(nums, 0, nums.Length - 1).Max;}public Range Partition(int[] nums, int i, int j) {if (i == j) return new Range(nums[i], nums[i], nums[i], nums[i]);int mid = (i + j) >> 1;return Partition(nums, i, mid) + Partition(nums, mid + 1, j);}
}
- 时间:76 ms,击败 94.44% 使用 C# 的用户
- 内存:38.25 MB,击败 77.78% 使用 C# 的用户
相关文章:
LeetCode 面试题 16.17. 连续数列
文章目录 一、题目二、C# 题解 一、题目 给定一个整数数组,找出总和最大的连续数列,并返回总和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。…...
基于人工蜂鸟算法的无人机航迹规划-附代码
基于人工蜂鸟算法的无人机航迹规划 文章目录 基于人工蜂鸟算法的无人机航迹规划1.人工蜂鸟搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要:本文主要介绍利用人工蜂鸟算法来优化无人机航迹规划。 …...
51单片机汇编-点亮一个led
文章目录 前言1.打开IDE2.设置编辑器3.设置输出4. 原理图5.编写代码6 编译7.下载8.其它代码1.LED闪烁2.跑马灯 前言 51单片机基础 51汇编实战 本章主要介绍打开一个led,具体采用51汇编 1.打开IDE 选择STC89C52RC 后缀是.asm 2.设置编辑器 3.设置输出 4. 原理图 5.编写代码 …...
每天一点python——day62
为了方便复制,我在下面附带了一个python文件。 C:\Users\Admin>python Python 3.9.13 (main, Aug 25 2022, 23:51:50) [MSC v.1916 64 bit (AMD64)] :: Anaconda, Inc. on win32Warning: This Python interpreter is in a conda environment, but the environmen…...
基于SSM的智慧作业试题管理系统(有报告)。Javaee项目。
演示视频: 基于SSM的智慧作业试题管理系统(有报告)。Javaee项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构,通过Spring Sprin…...
ESP32 未来能够取代 STM32吗?
今日话题,ESP32 未来能够取代 STM32吗?ESP32和STM32各自有其特点和优势,能否取代彼此取决于具体应用和需求。STM32的流行除了性价比外,还有其强大的开发环境,例如Cubemx能够快速生成代码,使得上手STM32的速…...
Java连接Redis并操作Redis中的常见数据类型
目录 一. Java连接Redis 1. 导入依赖 2. 建立连接 二. Java操作Redis的常见数据类型存储 1. Redis字符串(String) 2. Redis哈希(Hash) 3. Redis列表(List) 4. Redis集合(Set) 一. Java连接Redis 1. 导入依赖 pom依赖…...
Python 基于分位数-正态分布转换的评分算法
在实验的时候遇到一个比较实际的问题,就是怎样对数据进行评分。比如我想根据样本的正确率进行打分,有两种方法,一种是将准确率排序,然后根据序号进行打分,这样可以排除极端数据的影响,但是准确率之间的差距…...
如何修改CentOS登录时默认目录
查了一下,有说改/etc/passwd文件的,有说改.bashrc文件的,也有说改.bash_profile,修改的方法都不一样。 我要改的是root登录时的目录,最后修改了/root/.bash_profile文件,只要加一行cd 路径就可以。 这个文…...
JavaFX Scene Builder Gluon 控件详解
在 JavaFX Scene Builder 工具中,Gluon 是一个扩展库,提供了一些额外的控件和功能,用于创建更丰富和现代化的用户界面。本文将详细介绍 Gluon 中的各个控件及其作用。 AppBar(应用栏) AppBar 是一个用于显示应用程序…...
Vue路由(router-link)——高亮、动态传参
一、声明式导航-导航链接 1.需求 实现导航高亮效果 如果使用a标签进行跳转的话,需要给当前跳转的导航加样式,同时要移除上一个a标签的样式,太麻烦!!! 2.解决方案 vue-router 提供了一个全局组件 router…...
Java中将List转换为Map
在Java 8中,Stream API和Collectors类提供了一种方便的方式来处理集合数据。其中,将List转换为Map是一个常见的操作。下面我们将介绍如何使用Stream API和Collectors类将List转换为Map。 首先,假设我们有一个User类,包含id和name两…...
进程控制2——进程等待
在上一小节中我们介绍了进程的创建(fork)与退出(main函数的return与exit函数) 并且要有一个意识,进程退出的时候只有三种情况: 1.进程退出,结果正确 2.进程退出,结果不正确 3.运行异…...
k8s service
文章目录 Service 基础概念Service 类型:Service 的工作流程:东西流量,南北流量NodePortLoadBalancer Service 基础概念 在 Kubernetes(K8s)中,Service 是一个抽象的概念,表示一个应用程序的逻…...
C语言 每日一题 PTA 11.6 day12
1.调和平均 N 个正数的算数平均是这些数的和除以 N,它们的调和平均是它们倒数的算数平均的倒数。 本题就请你计算给定的一系列正数的调和平均值。 输入格式: 每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N(≤1000);第 2 行给…...
Git使用规范指南
文章目录 Git使用规范指南前言分支命名规范分支合并流程规范提交信息规范Angular提交规范注意事项 通用Git忽略文件配置 Git使用规范指南 前言 由于最近写完代码之后,Git使用不规范被领导说了,所以最近通过阅读大量的相关博客快速学习Git使用规范&#…...
axios和Ajax
1.axios 官网:https://axios-http.com/zh/ CDN:https://cdn.bootcdn.net/ajax/libs/axios/0.21.1/axios.min.js axios是一个请求库,在浏览器环境中,它封装了XHR,提供更加便捷的API发送请求 基本使用 // 发送 get 请求…...
Day06
1.继承 1.1 定义 让类与类之间产生子父类关系,有了继承性之后,子类就获取到了父类中声明的所有属性和方法。 1.2 优点 继承的出现减少了代码冗余,提高了代码的复用性。继承的出现,更有利于功能的扩展。继承的出现让类与类之间…...
@Tag和@Operation标签失效问题。SpringDoc 2.2.0(OpenApi 3)和Spring Boot 3.1.1集成
问题 Tag和Operation标签失效 但是Schema标签有效 pom依赖 <!-- 接口文档--><!--引入openapi支持--><dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-ui</artifactId><vers…...
基础课18——智能客服系统架构
1.基础设施层 基础设施主要包括以下几点: 1. 硬件设施:包括服务器、存储设备、网络设备等,这是整个系统运行的物理基础。 2. 软件设施:包括操作系统、数据库管理系统、自然语言处理(NLP)工具和机器学习算法等,这些是…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
