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

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.length
  • 1 <= 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 &#xff0c;返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上&#xff0c; nums[i] 的下一个元素是 nums[(i 1) % n] &#xff0c; nums[i] 的前一个元素是…...

AI算法图形化编程加持|OPT(奥普特)智能相机轻松适应各类检测任务

OPT&#xff08;奥普特&#xff09;基于SciVision视觉开发包&#xff0c;全新推出多功能一体化智能相机&#xff0c;采用图形化编程设计&#xff0c;操作简单、易用&#xff1b;不仅有上百种视觉检测算法加持&#xff0c;还支持深度学习功能&#xff0c;能轻松应对计数、定位、…...

C语言文件指针设置偏移量--fseek

一、fseek fseek是设置文件指针偏移量的函数&#xff0c;具体传参格式为&#xff1a; int fseek(FILE *stream, long int offset, int whence) 返回一个整数&#xff0c;其中&#xff1a; 1、stream是指向文件的指针 2、offset是偏移量&#xff0c;一般是指相对于whence的便…...

快速消除视频的原声的技巧分享

网络上下载的视频都会有视频原声或者背景音乐&#xff0c;如果不喜欢并且想更换新的BGM要怎么操作呢&#xff1f;今天小编就来教你如何快速给多个视频更换新的BGM&#xff0c;很简单&#xff0c;只需要将原视频的原声快速消音同时添加新的背景音频就行&#xff0c;一起来看看详…...

lua脚本实现Redis令牌桶限流

背景 令牌桶限流是一种常见的流量控制算法&#xff0c;用于控制系统的请求处理速率&#xff0c;防止系统过载。在令牌桶限流算法中&#xff0c;可以将请求看作是令牌&#xff0c;而令牌桶则表示系统的处理能力。系统在处理请求时&#xff0c;首先需要从令牌桶中获取令牌&#…...

最新 23 届计算机校招薪资汇总

24 届的秋招提前批已经开始了&#xff0c;比如米哈游、oppoe、tplink 等公司都已经录取开启提前批。 像腾讯、字节、阿里等一线大厂的话&#xff0c;根据往年的情况&#xff0c;估计是 7月下-8 月初。 所以今年参加秋招的同学&#xff0c;要抓紧复习了。 提前批通常就持续不到…...

BUU CODE REVIEW 1

BUU CODE REVIEW 1 考点&#xff1a;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的日志&#xff0c;如何认识日志&#xff0c;如何进行日志持久化&#xff0c;通过日志级别判断信息&#xff0c;了解Lombok插件的使用&#xff0c;通过Lombok自带注释更简洁的来完成日志打印&#xff0c;如有错误&#xff0c;请在评论区指正&#xff0…...

关于大规模数据处理的解决方案

大规模数据处理已经成为了现代商业和科学的核心。随着互联网普及和物联网技术的发展&#xff0c;越来越多的数据被收集和存储&#xff0c;这些数据包含了各种各样的信息&#xff0c;例如客户行为、传感器读数、社交媒体活动等等。这些数据的数量和复杂性已经超出了传统数据处理…...

免费快速下载省市区县行政区的Shp数据

摘要&#xff1a;一般非专业的GIS应用通常会用到省市等行政区区划边界空间数据做分析&#xff0c;本文简单介绍了如何在互联网上下载省&#xff0c;市&#xff0c;区县的shp格式空间边界数据&#xff0c;并介绍了一个好用的在线数据转换工具&#xff0c;并且开源。 一、首先&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时&#xff0c;有可能会发生数据倾斜&#xff0c;解决办法如下&#xff1a; 分组聚合 预聚合思想 map-side&#xff08;预聚合在map里面&#xff09;skew-groupby&#xff08;多个reduce阶段进行汇总&#xff09;&#xff1a;先对倾斜的key加上随机数&#x…...

Java多线程(三)

目录 一、Thread类基本用法 1.1 Thread常见构造方法 1.2 Thread常见属性 二、多线程常用的创建方式 2.1 继承Thread类 2.2 实现Runnable接口 2.3 继承Thread接口&#xff0c;使用匿名内部类 2.4实现Runnable接口&#xff0c;使用匿名内部类 2.5使用lambda表达式 三、线程的启动…...

Linux操作系统3-项目部署

手动部署 步骤 1.在idea中将文件项目进行打包 2.自定义一个文件目录&#xff0c;上传到Linux 3.使用 java -jar jar包名就可以进行运行 注意,如果需要启动该项目&#xff0c;需要确定所需的端口是否打开 采用这种方式&#xff0c;程序运行的时候会出现霸屏&#xff0c;并且会…...

软件测试面试题——接口自动化测试怎么做?

面试过程中&#xff0c;也问了该问题&#xff0c;以下是自己的回答&#xff1a; 接口自动化测试&#xff0c;之前做过&#xff0c;第一个版本是用jmeter 做的&#xff0c;1 主要是将P0级别的功能接口梳理出来&#xff0c;根据业务流抓包获取相关接口&#xff0c;并在jmeter中跑…...

如何在医疗器械行业运用IPD?

医疗器械是指单独或者组合使用于人体的仪器、设备、器具、材料或其他物品&#xff0c;包括所需要的软件。按安全性可分为低风险器械、中风险器械和高风险器械。其中低风险器械大都属于低值耗材&#xff0c;其中包括绷带、纱布、海绵、消毒液等&#xff1b;中度风险器械类包括体…...

16. Spring Boot 统一功能处理

目录 1. 用户登录权限校验 1.1 最初用户登录验证 1.2 Spring AOP 用户统一登陆验证 1.3 Spring 拦截器 1.3.1 创建自定义拦截器 1.3.2 将自定义拦截器加入系统配置 1.4 练习&#xff1a;登录拦截器 1.5 拦截器实现原理 1.6 统一访问前缀添加 2. 统一异常处理 3. 统…...

PostgreSQL-数据库命令

PostgreSQL-数据库命令 介绍 一个数据库是一个或多个模式的集合,而模式包含表、函数等。因此,完整的逻辑组织结构层次是服务器实例(PostgreSQL Server)、数据库(Database)、模式(Schema)、表(Table),以及某些其他对象(如函数)。一个PostgreSQL服务器实例可以管理…...

面试题:说说JavaScript中内存泄漏的几种情况?垃圾回收机制

内存泄漏 一、是什么&#xff1f;二、垃圾回收机制&#xff1f;2.1、标记清除法2.2、引用计数法 三、常见内存泄露情况 一、是什么&#xff1f; 由于疏忽或错误造成程序未能释放已经不再使用的内存&#xff1b;并非指内存在物理上的消失&#xff0c;而是应用程序分配某段内存后…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...