LeetCode 动态规划 环形子数组的最大和
环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], …, nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1:
输入:nums = [1,-2,3,-2]
输出:3
解释:从子数组 [3] 得到最大和 3
示例 2:
输入:nums = [5,-3,5]
输出:10
解释:从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3:
输入:nums = [3,-2,2,-3]
输出:3
解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示:
n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
题解
首先我们观察题目,不难发现这道题与53. 最大子数组和类似
唯一的区别就是本道题的数组是循环的,也就是首尾相连
那么这对我们分析题目有什么影响呢
正常情况,也就是没有利用首尾相连的情况
此时使用解最大子数组和的方法即可得到这种情况下的最大子数组
特殊情况,也就是利用了首尾相连的情况
此时数组可以看成两部分
前面与后面选中的部分与中间没有被选中的部分
我们可以发现,由于数组的总和是一定的
只要中间没有被选中的部分越小
那么我们选中的部分就越大,即这种情况下的最大子数组
所以只需要找到正常情况下的最小子数组,最大子数组的和就是 数组总和 - 最小子数组总和
求得正常情况下最小子数组与正常情况下最大子数组类似
特殊的,由于本道题目不允许空的子数组
所以当最小子数组是数组全体的话,特殊情况下求得的答案为0,即空数组
此时答案只能为正常情况下的答案
代码如下↓
Cint maxSubarraySumCircular(int* nums, int numsSize) {int max=-999999999;int min=999999999;int n=0;int m=0;int sum=0;for(int i=0;i<numsSize;i++){sum+=nums[i];if(n>0){n+=nums[i];}else{n=nums[i];}if(m<0){m+=nums[i];}else{m=nums[i];}if(n>max){max=n;}if(m<min){min=m;}}int res=fmax(max,sum-min);if(sum-min==0)//特殊情况,最小子数组为整个数组{res=max;}return res;
}
时间复杂度: O(n)
空间复杂度: O(1)
相关文章:
LeetCode 动态规划 环形子数组的最大和
环形子数组的最大和 给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i 1) % n] , nums[i] 的前一个元素是 nums[(…...
毕业项目推荐:基于yolov8/yolo11的野生菌菇检测识别系统(python+卷积神经网络)
文章目录 概要一、整体资源介绍技术要点功能展示:功能1 支持单张图片识别功能2 支持遍历文件夹识别功能3 支持识别视频文件功能4 支持摄像头识别功能5 支持结果文件导出(xls格式)功能6 支持切换检测到的目标查看 二、数据集三、算法介绍1. YO…...
基于开源鸿蒙(OpenHarmony)的【智能家居综合应用】系统
基于开源鸿蒙OpenHarmony的智能家居综合应用系统 1. 智能安防与门禁系统1) 系统概述2) 系统架构3)关键功能实现4)安全策略5)总结 2.环境智能调节系统1)场景描述2)技术实现3)总结 3.健康管理与睡眠监测1&…...
C语言【指针篇】(三)
C语言【指针篇】(三) 前言正文1. 数组名的理解2. 使用指针访问数组3. 一维数组传参的本质4. 冒泡排序5. 二级指针6. 指针数组7. 指针数组模拟二维数组 总结 前言 本文主要基于前面对指针的掌握,进一步学习:数组名的理解、使用指针…...
【嵌入式Linux应用开发基础】网络编程(4):UDP协议
目录 一、UDP 协议概述 二、UDP 协议特点 三、UDP协议的字段格式 四、UDP协议的数据传输过程 五、嵌入式UDP编程核心API 六、UDP 在嵌入式 Linux 中的编程实现 6.1 UDP 服务器代码示例 6.2 UDP 客户端代码示例 七、UDP 协议的应用场景 八、UDP 协议的优缺点 8.1 优点…...
PS渐变工具
渐变工具:(颜色条 起点到终点 为 前景色到背景色) 渐变shift:垂直、水平、45度 渐变工具–》仿色:让渐变变得细腻。仿色值高,过渡柔和,仿色值低,过渡粗糙 渐变工具–》渐变编辑器&am…...
win11系统通过WSL安装ubuntu
Linux 和Windows windows 属于单用户、多任务 Linux属于多用户多任务。Linux一切皆文件 https://blog.csdn.net/ddafei/article/details/142798010 一、启用WSL功能 首先,你需要在Windows上启用WSL功能。 打开“控制面板”。点击“程序” > “启用或关闭Windo…...
Sqoop从入门到使用
安装和配置 修改文件配置:修改文件名将(sqoop-env-template.sh改为sqoop-env.sh) 编辑sqoop-env.sh内部文本,修改调用文件位置 将sqoop-env.sh,配置到全局变量中,方便调用。 查看正常运用 第一类࿱…...
深度学习奠基作 AlexNet 论文阅读笔记(2025.2.25)
文章目录 训练数据集数据预处理神经网络模型模型训练正则化技术模型性能其他补充 训练数据集 模型主要使用2010年和2012年的 ImageNet 大规模视觉识别挑战赛(ILSVRC)提供的 ImageNet 的子集进行训练,这些子集包含120万张图像。最终ÿ…...
解决python项目无法安装openai模块的问题
问题描述: pip install openai Fatal error in launcher: Unable to create process using ‘“e:\private\github\navigation_site.venv\Scripts\python.exe” “E:\private\github\my_project\navigation_site.venv\Scripts\pip.exe” install OpenAI’: ??? 这…...
项目实践 之 pdf简历的解析和填充(若依+vue3)
文章目录 环境背景最终效果前端讲解左侧模块解析右侧上传模块解析前端步骤 后端讲解代码前端 环境背景 若依前后端分离框架 vue最后边附有代码哦 最终效果 前端讲解 左侧模块解析 1、左侧表单使用el-form 注意: 1、prop出现的字段,需要保证是该类所…...
RAGS评测后的数据 如何利用influxdb和grafan 进行数据汇总查看
RAGS(通常指相关性、准确性、语法、流畅性)评测后的数据能借助 InfluxDB 存储,再利用 Grafana 进行可视化展示,实现从四个维度查看数据,并详细呈现每个问题对应的这四个指标情况。以下是详细步骤: 1. 环境准备 InfluxDB 安装与配置 依据自身操作系统,从 InfluxDB 官网下…...
本地部署阿里的万象2.1文生视频(Wan2.1-T2V-1.3B)模型
文章目录 (零)在线体验(一)本地部署(1.1)克隆仓库(1.2)安装依赖(1.2.1)安装 flash-attention(1.2.2)重新安装依赖(1.2.3&a…...
centos设置 sh脚本开机自启动
1. start.sh脚本 #!/bin/bash# 依赖docker,等待xxx容器完全启动 sleep 60curl -X POST "localhost:8381/models?urlmymodel.mar&model_namemymodel&batch_size1&max_batch_delay10&initial_workers1"sudo /usr/local/nginx/sbin/nginx …...
一文读懂什么是K8s Admission Controller
#作者:曹付江 文章目录 1、什么是 Admission Controllers?2、如何创建 Admission Controllers?3、Admission 控制器的最佳实践 K8s 中的操作与安全标准执行机制: 1、什么是 Admission Controllers? Admission contro…...
江协科技/江科大-51单片机入门教程——P[1-3] 单片机及开发板介绍
前言:本节主要的任务是了解一下 51 单片机和所用的普中51开发板。 目录 一、单片机介绍 二、单片机的应用领域 三、STC89C52单片机 四、命名规则 五、单片机内部拆解 六、单片机内部结构图 七、单片机管脚图 八、单片机最小系统 九、开发板介绍 十、开发…...
一周学会Flask3 Python Web开发-Jinja2模板继承和include标签使用
锋哥原创的Flask3 Python Web开发 Flask3视频教程: 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 不管是开发网站还是后台管理系统,我们页面里多多少少有公共的模块。比如博客网站,就有公共的头部&…...
4.3MISC流量分析练习-wireshark-https
流量分析题目的例题 1.了解wireshark的过滤方式 2.了解tls跟ssl协议基本还原 3.了解xor基本变换方式,获取flag 附件是一个流量包,打开之后有各种流量,但是分析无果,然后丢到kali中使用binwalk进行分析,发现有一个r…...
wifi5和wifi6,WiFi 2.4G、5G,五类网线和六类网线,4G和5G的区别
wifi5和wifi6的区别 是Wi-Fi 5和Wi-Fi 6的选择与路由器密切相关。路由器是创建和管理无线网络的设备,它决定了网络的类型和性能。具体来说: 路由器的标准支持:路由器可以支持不同的Wi-Fi标准,如Wi-Fi 5(802.11ac)和Wi-Fi 6(802.11ax)。支持Wi-Fi 6的路由器能够提供更高…...
【二分查找】P9698 [GDCPC2023] Path Planning|普及
本文涉及的基础知识点 本博文代码打包下载 C二分查找 [GDCPC2023] Path Planning 题面翻译 【题目描述】 有一个 n n n 行 m m m 列的网格。网格里的每个格子都写着一个整数,其中第 i i i 行第 j j j 列的格子里写着整数 a i , j a_{i, j} ai,j。从 0…...
请介绍一下Java的面向对象特性
Java是一种纯面向对象的语言,它支持类、继承、封装和多态等面向对象的基本概念。以下是Java面向对象特性的详细介绍: 一、封装 封装是面向对象编程的核心思想之一,它指的是将对象的属性和方法结合在一起,并隐藏对象的内部实现细…...
使用ZFile打造属于自己的私有云系统结合内网穿透实现安全远程访问
文章目录 前言1.关于ZFile2.本地部署ZFile3.ZFile本地访问测试4.ZFile的配置5.cpolar内网穿透工具安装6.创建远程连接公网地址7.固定ZFile公网地址 前言 在数字化的今天,我们每个人都是信息的小能手。无论是职场高手、摄影达人还是学习狂人,每天都在创造…...
Spring 源码硬核解析系列专题(八):Spring Security 的认证与授权源码解析
在前几期中,我们从 Spring 核心到 Spring Boot,再到 Spring Cloud,逐步探索了 Spring 生态的底层原理。作为企业级应用的关键组件,Spring Security 提供了全面的安全解决方案,包括认证(Authentication)和授权(Authorization)。本篇将深入 Spring Security 的源码,剖析…...
Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(七)
亮度数据 为了确保用户不会因为切换而注意到亮度变化,GPU0 和 GPU1 显示的所有亮度属性都必须相同。 此要求可确保在切换 GPU0 至 GPU1 之前的任何亮度级别,在切换至 GPU1 后都可以支持。 为此,GPU0 和 GPU1 的驱动程序必须: 使…...
Android ObjectBox数据库使用与集成指南
ObjectBox其核心特点ObjectBox与 SQLite 和 Realm 的对比Android集成ObjectBox创建ObjectBox实体对象创建ObjectBox操作管理类OBManager在Application初始化ObjectBox插入或更新数据查询数据统计数据分页数据查询删除数据总结今天分享一套Android另一个数据库ObjectBox。Object…...
C++ Qt常见面试题(3):Qt内存管理机制
Qt 内存管理机制是其框架的重要组成部分,目的是简化开发者对内存的管理,减少内存泄漏的风险,同时提供高效的资源使用方式。Qt 的内存管理机制主要依赖于 对象树(Object Tree) 和 父子关系(Parent-Child Relationship) 的设计,通过智能管理对象的生命周期来实现自动化的…...
到底什么是认证?
哈喽!欢迎来到程序视点,我是小二哥!本店菜品如下: #风暴过后以桶 认证和授权 什么是认证 认证 (Authentication) 是根据凭据验明访问者身份的流程。即验证“你是你所说的那个人”的过程。 身份认证,通常通过用户名…...
量子计算可能改变世界的四种方式
世界各地的组织和政府正将数十亿美元投入到量子研究与开发中,谷歌、微软和英特尔等公司都在竞相实现量子霸权。 这其中的利害关系重大,有这么多重要的参与者,量子计算机的问世可能指日可待。 为做好准备,,我们必须了…...
【Web安全】图片验证码DOS漏洞
文章目录 免责声明一、漏洞原理二、测试步骤三、测试案例四、修复方式免责声明 在网络安全领域,技术文章应谨慎使用,遵守法律法规,严禁非法网络活动。未经授权,不得利用文中信息进行入侵,造成的任何后果,由使用者自行承担,本文作者不负责。提供的工具仅限学习使用,严禁…...
鸿蒙Next如何自定义标签页
前言 项目需求是展示标签,标签的个数不定,一行展示不行就自行换行。但是,使用鸿蒙原生的 Grid 后发现特别的难看。然后就想着自定义控件。找了官方文档,发现2个重要的实现方法,但是,官方的demo中讲的很少&…...
一周学会Flask3 Python Web开发-Jinja2模板过滤器使用
锋哥原创的Flask3 Python Web开发 Flask3视频教程: 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 在Jinja2中,过滤器(filter)是一些可以用来修改和过滤变量值的特殊函数,过滤器和变量用一个竖线 | &a…...
HarmonyOS 5.0应用开发——鸿蒙接入高德地图实现POI搜索
【高心星出品】 文章目录 鸿蒙接入高德地图实现POI搜索运行结果:准备地图编写ArkUI布局来加载HTML地图 鸿蒙接入高德地图实现POI搜索 在当今数字化时代,地图应用已成为移动设备中不可或缺的一部分。随着鸿蒙系统的日益普及,如何在鸿蒙应用中…...
浅谈HTTP及HTTPS协议
1.什么是HTTP? HTTP全称是超文本传输协议,是一种基于TCP协议的应用非常广泛的应用层协议。 1.1常见应用场景 一.浏览器与服务器之间的交互。 二.手机和服务器之间通信。 三。多个服务器之间的通信。 2.HTTP请求详解 2.1请求报文格式 我们首先看一下…...
内存泄漏指什么?常见的内存泄漏有哪些?
内存泄漏是指程序在运行过程中,由于某些原因导致程序无法释放已经不再使用的内存,使得这部分内存持续被占用,最终可能导致系统可用内存逐渐减少,严重时会影响系统性能甚至导致程序崩溃。(内存泄漏是指程序中已经分配的…...
FFmpeg视频处理入门级教程
一、FFmpeg常规处理流程 #mermaid-svg-W8X1llNEyuYptV3I {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-W8X1llNEyuYptV3I .error-icon{fill:#552222;}#mermaid-svg-W8X1llNEyuYptV3I .error-text{fill:#552222;str…...
PINN求解固体力学问题——论文加代码
PINN求解固体力学问题——论文加代码 1. 训练2. 可视化 论文:Physics-Informed Deep Learning and its Application in Computational Solid and Fluid Mechanics 1. 训练 # %load Plane_Stress_W-PINNs.py """ Forward Problem for Plane Stress …...
HC32F460_SCI驱动(一)
在开始介绍HC32F460的SCI驱动之前,先重点说明一下功能组与串口相关参数,以便于更好的描述SCI驱动。 1. 功能组 1.1 基本概念 HC32F460的引脚功能复用机制通过Func_Grp(功能组)实现,其灵活性显著高于传统单片机(如STM32系列)。每个引脚支持多种外设功能,具体功能通过选…...
程序诗篇里的灵动笔触:指针绘就数据的梦幻蓝图
大家好啊,我是小象٩(๑ω๑)۶ 我的博客:Xiao Xiangζั͡ޓއއ 很高兴见到大家,希望能够和大家一起交流学习,共同进步。 这一节我们来学习指针的相关知识,学习内存和地址,指针变量和地址,包…...
QT:QPen、QBrush、与图形抗锯齿的关联
QPen QPen 是 Qt 框架中用于定义绘图时使用的画笔属性的类。在使用 QPainter 进行 2D 绘图时,QPen 可以控制线条的外观,比如线条的颜色、宽度、样式(如实线、虚线等)、端点样式(如方形端点、圆形端点等)和…...
数据结构秘籍(一)线性数据结构
1.数组 数组(Array)是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引(index)计算出该元素对应的存储地址。 数组的特…...
【数据分享】2000-2024年全国逐年归一化植被指数(NDVI)栅格数据(年平均值)
NDVI,全名为Normalized Difference Vegetation Index,中文名称为归一化植被指数。这个指数可以用来定性和定量评价植被覆盖及其生长活力,我们也可以简单地将它理解为体现植被密度和健康状况的一个指标。 之前我们给大家分享了来源于MOD13A3数…...
解决前端计算的浮点精度问题
问题:比如1001*1.11等于110.11 但是如果用前端开发处理的话 ,因为涉及到浮点数运算(这是因为JavaScript(以及其他许多编程语言)使用IEEE 754标准来表示浮点数,导致某些十进制小数无法精确表示,…...
C语言基本知识------指针(4)
1. 回调函数是什么? 回调函数就是⼀个通过函数指针调用的函数。 如果你把函数的指针(地址)作为参数传递给另⼀个函数,当这个指针被⽤来调⽤其所指向的函数 时,被调⽤的函数就是回调函数。 void qsort(void base,//指针…...
004 Kafka异常处理
6.异常处理 文章目录 6.异常处理1.异常分类与处理原则2.生产者异常处理1. 同步发送捕获异常2. 异步发送回调处理 3.消费者异常处理1.全局异常处理器2.方法级处理3.重试yml配置 4.死信队列(DLQ)配置1. 启用死信队列2. 手动发送到DLQ 5.事务场景异常处理1.…...
C++模拟实现map和set
C模拟实现map和set 1、STL源代码分析2、实现出复用红黑树的框架3、实现红黑树的迭代器4、解决map和set中key不可修改问题5、解决insert返回值问题完整代码 模拟实现map和set实际上是对红黑树的封装,如对红黑树的实现有疑问,请移步:C手撕红黑树…...
使用elasticdump导出/导入 -- ES数据
导出指定索引数据到指定文件夹: ./elasticdump --inputhttp://用户:密码IP:9201/索引名字 --output导出路径/out.json --typedata 将导出的文件导入 ./elasticdump --input路径/out.json --outputhttp://账号:密码IP:9201/索引名称 --typedata --fileTypejson 【el…...
CSDN年度评选揭晓,永洪科技AI技术与智能应用双星闪耀
近日,永洪科技在CSDN(中国专业开发者社区)的年度评选中,凭借在人工智能技术创新与vividime在行业应用中的卓越表现,一举斩获“人工智能企业”及“智能应用”双料大奖。这一荣誉不仅彰显了永洪科技在AI领域的领先地位&a…...
Kubernetes 资源利用率翻倍?离在线混合部署深度解析
还在为 Kubernetes 集群资源利用率低而烦恼?还在为高昂的云成本而头疼?今天,我们就来聊聊 Kubernetes 中的一项黑科技——离在线混合部署,让大家的集群资源利用率翻倍,成本减半! 🤔 什么是离在线…...
【Java】Spring Boot全量YAML配置说明
目录 Spring Boot 配置文件基础核心配置日志配置Web 服务器配置数据源配置JPA 配置缓存配置国际化配置邮件服务配置自定义配置使用示例1. Spring Boot 配置文件基础 Spring Boot 的配置文件可以使用以下文件格式: application.propertiesapplication.ymlSpring Boot 默认加载…...
【STL】7.STL常用算法(1)
STL常用算法(1) 前言简介一.遍历算法1.for_each2.transform 二.查找算法1.find2.find_if3.adjacent_find4.binary_search5.count6.cout_if 三.排序算法1.sort2.random_shuffle3.merge4.reverse 总结 前言 stl系列主要讲述有关stl的文章,使用S…...