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)工具和机器学习算法等,这些是…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
