当前位置: 首页 > 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 Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...