918. 环形子数组的最大和
918. 环形子数组的最大和
给定一个长度为 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.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<vector<int>> dp(n,vector<int>(2,nums[0]));dp[0][0]=nums[0];dp[0][1]=nums[0];int sum=nums[0],maxn=nums[0],minn=nums[0];for(int i=1;i<n;i++){//每个元素都当做是子数组的最后一个元素,分别求出两个状态,最大子数组和和最小子数组和dp[i][0]=max(dp[i-1][0]+nums[i],nums[i]);maxn=max(dp[i][0],maxn);dp[i][1]=min(dp[i-1][1]+nums[i],nums[i]);minn=min(dp[i][1],minn);sum+=nums[i];}return maxn>0?max(maxn,sum-minn):maxn;}
};
相关文章:
918. 环形子数组的最大和
918. 环形子数组的最大和 给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i 1) % n] , nums[i] 的前一个元素是…...
AI算法图形化编程加持|OPT(奥普特)智能相机轻松适应各类检测任务
OPT(奥普特)基于SciVision视觉开发包,全新推出多功能一体化智能相机,采用图形化编程设计,操作简单、易用;不仅有上百种视觉检测算法加持,还支持深度学习功能,能轻松应对计数、定位、…...
C语言文件指针设置偏移量--fseek
一、fseek fseek是设置文件指针偏移量的函数,具体传参格式为: int fseek(FILE *stream, long int offset, int whence) 返回一个整数,其中: 1、stream是指向文件的指针 2、offset是偏移量,一般是指相对于whence的便…...
快速消除视频的原声的技巧分享
网络上下载的视频都会有视频原声或者背景音乐,如果不喜欢并且想更换新的BGM要怎么操作呢?今天小编就来教你如何快速给多个视频更换新的BGM,很简单,只需要将原视频的原声快速消音同时添加新的背景音频就行,一起来看看详…...
lua脚本实现Redis令牌桶限流
背景 令牌桶限流是一种常见的流量控制算法,用于控制系统的请求处理速率,防止系统过载。在令牌桶限流算法中,可以将请求看作是令牌,而令牌桶则表示系统的处理能力。系统在处理请求时,首先需要从令牌桶中获取令牌&#…...
最新 23 届计算机校招薪资汇总
24 届的秋招提前批已经开始了,比如米哈游、oppoe、tplink 等公司都已经录取开启提前批。 像腾讯、字节、阿里等一线大厂的话,根据往年的情况,估计是 7月下-8 月初。 所以今年参加秋招的同学,要抓紧复习了。 提前批通常就持续不到…...
BUU CODE REVIEW 1
BUU CODE REVIEW 1 考点:PHP变量引用 源码直接给了 <?phphighlight_file(__FILE__);class BUU {public $correct "";public $input "";public function __destruct() {try {$this->correct base64_encode(uniqid());if($this->c…...
django使用ztree实现树状结构效果,子节点实现动态加载(l懒加载)
一、实现的效果 由于最近项目中需要实现树状结构的效果,考虑到ztree这个组件大家用的比较多,因此打算在django项目中集成ztree来实现树状的效果。最终实现的示例效果如下: 点击父节点,如果有子节点,则从后台动态请求数据,然后显示出子节点的数据。 二、实现思路 …...
认识springboot 之 了解它的日志 -4
前言 本篇介绍springboot的日志,如何认识日志,如何进行日志持久化,通过日志级别判断信息,了解Lombok插件的使用,通过Lombok自带注释更简洁的来完成日志打印,如有错误,请在评论区指正࿰…...
关于大规模数据处理的解决方案
大规模数据处理已经成为了现代商业和科学的核心。随着互联网普及和物联网技术的发展,越来越多的数据被收集和存储,这些数据包含了各种各样的信息,例如客户行为、传感器读数、社交媒体活动等等。这些数据的数量和复杂性已经超出了传统数据处理…...
免费快速下载省市区县行政区的Shp数据
摘要:一般非专业的GIS应用通常会用到省市等行政区区划边界空间数据做分析,本文简单介绍了如何在互联网上下载省,市,区县的shp格式空间边界数据,并介绍了一个好用的在线数据转换工具,并且开源。 一、首先&am…...
MAC下配置android-sdk
MAC下配置android-sdk 1、前提2、brew安装3、配置sdk 1、前提 安装好JDK安装brew 2、brew安装 brew install android-sdk brew install android-platform-tools检查是否安装成功 android3、配置sdk brew list android-sdk进入配置文件 sudo vim ~/.zshrc配置 export AND…...
Hive-数据倾斜
在计算各省份的GMV时,有可能会发生数据倾斜,解决办法如下: 分组聚合 预聚合思想 map-side(预聚合在map里面)skew-groupby(多个reduce阶段进行汇总):先对倾斜的key加上随机数&#x…...
Java多线程(三)
目录 一、Thread类基本用法 1.1 Thread常见构造方法 1.2 Thread常见属性 二、多线程常用的创建方式 2.1 继承Thread类 2.2 实现Runnable接口 2.3 继承Thread接口,使用匿名内部类 2.4实现Runnable接口,使用匿名内部类 2.5使用lambda表达式 三、线程的启动…...
Linux操作系统3-项目部署
手动部署 步骤 1.在idea中将文件项目进行打包 2.自定义一个文件目录,上传到Linux 3.使用 java -jar jar包名就可以进行运行 注意,如果需要启动该项目,需要确定所需的端口是否打开 采用这种方式,程序运行的时候会出现霸屏,并且会…...
软件测试面试题——接口自动化测试怎么做?
面试过程中,也问了该问题,以下是自己的回答: 接口自动化测试,之前做过,第一个版本是用jmeter 做的,1 主要是将P0级别的功能接口梳理出来,根据业务流抓包获取相关接口,并在jmeter中跑…...
如何在医疗器械行业运用IPD?
医疗器械是指单独或者组合使用于人体的仪器、设备、器具、材料或其他物品,包括所需要的软件。按安全性可分为低风险器械、中风险器械和高风险器械。其中低风险器械大都属于低值耗材,其中包括绷带、纱布、海绵、消毒液等;中度风险器械类包括体…...
16. Spring Boot 统一功能处理
目录 1. 用户登录权限校验 1.1 最初用户登录验证 1.2 Spring AOP 用户统一登陆验证 1.3 Spring 拦截器 1.3.1 创建自定义拦截器 1.3.2 将自定义拦截器加入系统配置 1.4 练习:登录拦截器 1.5 拦截器实现原理 1.6 统一访问前缀添加 2. 统一异常处理 3. 统…...
PostgreSQL-数据库命令
PostgreSQL-数据库命令 介绍 一个数据库是一个或多个模式的集合,而模式包含表、函数等。因此,完整的逻辑组织结构层次是服务器实例(PostgreSQL Server)、数据库(Database)、模式(Schema)、表(Table),以及某些其他对象(如函数)。一个PostgreSQL服务器实例可以管理…...
面试题:说说JavaScript中内存泄漏的几种情况?垃圾回收机制
内存泄漏 一、是什么?二、垃圾回收机制?2.1、标记清除法2.2、引用计数法 三、常见内存泄露情况 一、是什么? 由于疏忽或错误造成程序未能释放已经不再使用的内存;并非指内存在物理上的消失,而是应用程序分配某段内存后…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
