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

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[j1]+nums[j],max[j1],nums[j],nums[j]>0nums[j]0max[j1]<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 中情况:

  1. 在 left 中。
  2. 在 right 中。
  3. 在 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# 题解 一、题目 给定一个整数数组&#xff0c;找出总和最大的连续数列&#xff0c;并返回总和。 示例&#xff1a; 输入&#xff1a; [-2,1,-3,4,-1,2,1,-5,4] 输出&#xff1a; 6 解释&#xff1a; 连续子数组 [4,-1,2,1] 的和最大&#xff0c;为 6。…...

基于人工蜂鸟算法的无人机航迹规划-附代码

基于人工蜂鸟算法的无人机航迹规划 文章目录 基于人工蜂鸟算法的无人机航迹规划1.人工蜂鸟搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用人工蜂鸟算法来优化无人机航迹规划。 …...

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

为了方便复制&#xff0c;我在下面附带了一个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项目。

演示视频&#xff1a; 基于SSM的智慧作业试题管理系统&#xff08;有报告&#xff09;。Javaee项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Sprin…...

ESP32 未来能够取代 STM32吗?

今日话题&#xff0c;ESP32 未来能够取代 STM32吗&#xff1f;ESP32和STM32各自有其特点和优势&#xff0c;能否取代彼此取决于具体应用和需求。STM32的流行除了性价比外&#xff0c;还有其强大的开发环境&#xff0c;例如Cubemx能够快速生成代码&#xff0c;使得上手STM32的速…...

Java连接Redis并操作Redis中的常见数据类型

目录 一. Java连接Redis 1. 导入依赖 2. 建立连接 二. Java操作Redis的常见数据类型存储 1. Redis字符串(String) 2. Redis哈希(Hash) 3. Redis列表&#xff08;List&#xff09; 4. Redis集合&#xff08;Set&#xff09; 一. Java连接Redis 1. 导入依赖 pom依赖…...

Python 基于分位数-正态分布转换的评分算法

在实验的时候遇到一个比较实际的问题&#xff0c;就是怎样对数据进行评分。比如我想根据样本的正确率进行打分&#xff0c;有两种方法&#xff0c;一种是将准确率排序&#xff0c;然后根据序号进行打分&#xff0c;这样可以排除极端数据的影响&#xff0c;但是准确率之间的差距…...

如何修改CentOS登录时默认目录

查了一下&#xff0c;有说改/etc/passwd文件的&#xff0c;有说改.bashrc文件的&#xff0c;也有说改.bash_profile&#xff0c;修改的方法都不一样。 我要改的是root登录时的目录&#xff0c;最后修改了/root/.bash_profile文件&#xff0c;只要加一行cd 路径就可以。 这个文…...

JavaFX Scene Builder Gluon 控件详解

在 JavaFX Scene Builder 工具中&#xff0c;Gluon 是一个扩展库&#xff0c;提供了一些额外的控件和功能&#xff0c;用于创建更丰富和现代化的用户界面。本文将详细介绍 Gluon 中的各个控件及其作用。 AppBar&#xff08;应用栏&#xff09; AppBar 是一个用于显示应用程序…...

Vue路由(router-link)——高亮、动态传参

一、声明式导航-导航链接 1.需求 实现导航高亮效果 如果使用a标签进行跳转的话&#xff0c;需要给当前跳转的导航加样式&#xff0c;同时要移除上一个a标签的样式&#xff0c;太麻烦&#xff01;&#xff01;&#xff01; 2.解决方案 vue-router 提供了一个全局组件 router…...

Java中将List转换为Map

在Java 8中&#xff0c;Stream API和Collectors类提供了一种方便的方式来处理集合数据。其中&#xff0c;将List转换为Map是一个常见的操作。下面我们将介绍如何使用Stream API和Collectors类将List转换为Map。 首先&#xff0c;假设我们有一个User类&#xff0c;包含id和name两…...

进程控制2——进程等待

在上一小节中我们介绍了进程的创建&#xff08;fork&#xff09;与退出&#xff08;main函数的return与exit函数&#xff09; 并且要有一个意识&#xff0c;进程退出的时候只有三种情况&#xff1a; 1.进程退出&#xff0c;结果正确 2.进程退出&#xff0c;结果不正确 3.运行异…...

k8s service

文章目录 Service 基础概念Service 类型&#xff1a;Service 的工作流程&#xff1a;东西流量&#xff0c;南北流量NodePortLoadBalancer Service 基础概念 在 Kubernetes&#xff08;K8s&#xff09;中&#xff0c;Service 是一个抽象的概念&#xff0c;表示一个应用程序的逻…...

C语言 每日一题 PTA 11.6 day12

1.调和平均 N 个正数的算数平均是这些数的和除以 N&#xff0c;它们的调和平均是它们倒数的算数平均的倒数。 本题就请你计算给定的一系列正数的调和平均值。 输入格式&#xff1a; 每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N(≤1000)&#xff1b;第 2 行给…...

Git使用规范指南

文章目录 Git使用规范指南前言分支命名规范分支合并流程规范提交信息规范Angular提交规范注意事项 通用Git忽略文件配置 Git使用规范指南 前言 由于最近写完代码之后&#xff0c;Git使用不规范被领导说了&#xff0c;所以最近通过阅读大量的相关博客快速学习Git使用规范&#…...

axios和Ajax

1.axios 官网&#xff1a;https://axios-http.com/zh/ CDN&#xff1a;https://cdn.bootcdn.net/ajax/libs/axios/0.21.1/axios.min.js axios是一个请求库&#xff0c;在浏览器环境中&#xff0c;它封装了XHR&#xff0c;提供更加便捷的API发送请求 基本使用 // 发送 get 请求…...

Day06

1.继承 1.1 定义 让类与类之间产生子父类关系&#xff0c;有了继承性之后&#xff0c;子类就获取到了父类中声明的所有属性和方法。 1.2 优点 继承的出现减少了代码冗余&#xff0c;提高了代码的复用性。继承的出现&#xff0c;更有利于功能的扩展。继承的出现让类与类之间…...

@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.基础设施层 基础设施主要包括以下几点&#xff1a; 1. 硬件设施&#xff1a;包括服务器、存储设备、网络设备等&#xff0c;这是整个系统运行的物理基础。 2. 软件设施&#xff1a;包括操作系统、数据库管理系统、自然语言处理(NLP)工具和机器学习算法等&#xff0c;这些是…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...