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

LeetCode环形子数组的最大和(编号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

二.解题思路

动态规划解法:

   

    g[i] 表示以i位置为结尾的所有子数组的最小和

    环形数组的子数组的最大和有两种情况:

    1.拥有最大和的子数组就在数组的中间

    2.环形数组的头部和尾部共同组成了拥有最大和的子数组

    我们只需要求两种情况的最大值,再确定哪种更大返回即可

    对于1:

     f[i] 表示以i位置为结尾的所有子数组的最大和

     当长度为1时,子数组的最大和为nums[i]

     当长度大于1时,子数组的最大和nums[i]+f[i-1]

    状态转移方程: f[i]=Math.max(nums[i],f[i-1]);

    对于2:

    转化为求数组中间的最小子数组和,用数组总和sum-数组中间的最小子数组和(gmin)

    同理:

    最小和的状态转移方程: g[i]=Math.min(nums[i],g[i-1]);

    初始化:可以添加一个虚拟的头部,在状态数组里多开一个空间,填入0

     可以使填了0可以使原来的结果不变,f[0]=g[0]=0,

     循环填状态方程时就可以直接从1开始,状态数组多加了一个格子,注意下标映射

     原数组nums[i]变成nums[i-1]

     返回值:注意如果数组全部为负数如 [-1,-2,-3],

     那么最大的子数组应该在数组中间,直接返回fmax

三.解题代码

public int maxSubarraySumCircular(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];int fmax=Integer.MIN_VALUE;int gmin=Integer.MAX_VALUE;int sum=0;for(int i=1;i<=n;i++){sum+=nums[i-1]; //求总数组和f[i] = Math.max(nums[i-1],nums[i-1] + f[i-1]);fmax = Math.max(fmax,f[i]);//求数组中间的最大子数组和g[i] = Math.min(nums[i-1],nums[i-1] + g[i-1]);gmin = Math.min(gmin,g[i]);//求数组中间的最小子数组和} //判断数组是否全为负数,如果是直接返回fmax,不是判断1,2情况哪个大return  sum==gmin ? fmax:Math.max(fmax,sum-gmin);}
}

 

相关文章:

LeetCode环形子数组的最大和(编号918)

目录 一.题目 二.解题思路 三.解题代码 一.题目 918. 环形子数组的最大和 给定一个长度为 n 的环形整数数组 nums &#xff0c;返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上&#xff0c; nums[i] 的下一个元素是 nums[…...

PhpOffice/PhpSpreadsheet读取和写入Excel

PhpSpreadsheet是一个纯PHP编写的组件库&#xff0c;它使用现代PHP写法&#xff0c;代码质量和性能比PHPExcel高不少&#xff0c;完全可以替代PHPExcel&#xff08;PHPExcel已不再维护&#xff09;。使用PhpSpreadsheet可以轻松读取和写入Excel文档&#xff0c;支持Excel的所有…...

jenkins自动化部署Jenkinsfile文件配置

简介 使用jenkins部署时会读取项目中Jenkinsfile文件&#xff0c;文件配置不对会导致部署失败 文件内容 pipeline {agent anyparameters {string(name: project_name, defaultValue: xxx1, description: 项目jar名称)string(name: version, defaultValue: xxx2, description…...

【socket编程简述】TCP UDP 通信总结、TCP连接的三次握手、TCP断开的四次挥手

Socket&#xff1a;Socket被称做 套接字&#xff0c;是网络通信中的一种约定。 Socket编程的应用无处不在&#xff0c;我们平时用的QQ、微信、浏览器等程序.都与Socket编程有关。 三次握手 四次断开 面试可…...

多线程-死锁

/*** 死锁demo*/ public class DeadlockDemo {public static void main(String[] args) {// 创建两个对象final Object resource1 "resource1";final Object resource2 "resource2";// 创建第一个线程Thread t1 new Thread(() -> {// 尝试锁定resour…...

P1006 [NOIP2008 提高组] 传纸条

P1006 [NOIP2008 提高组] 传纸条 题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路四维dp三维dp AC四维代码&#xff1a;AC三维代码&#xff1a; 题目描述 小渊和小轩是好朋友也是同班同学&#xff0c;他们在一起总有谈不完的话题。一次素质拓展活动中&#…...

杭电比赛总结

我们的队伍&#xff1a;team013 另外两队&#xff1a;team014、team015 ​ 今天是我第一次打杭电&#xff0c;发现杭电多数都是猜结论题 先给一下我们的提交数据 Submit TimeProblem IDTimeMemoryJudge Status4:59:59101115 MS1692 KWrong Answer4:59:55101115 MS1684 KWrong…...

dom靶场

靶场下载地址&#xff1a; https://www.vulnhub.com/entry/domdom-1,328/ 一、信息收集 获取主机ip nmap -sP 192.168.16.0/24netdiscover -r 192.168.16.0/24端口版本获取 nmap -sV -sC -A -p 1-65535 192.168.16.209开放端口只有80 目录扫描 这里扫描php后缀的文件 g…...

go struct 的常见问题

go struct 的常见问题 1. 什么是struct&#xff1f;2. 如何声明、定义和创建一个struct&#xff1f;3. struct和其他数据类型&#xff08;如数组、切片、map等&#xff09;有什么区别&#xff1f;4. 如何访问struct字段&#xff1f;5. struct是否支持继承&#xff0c;是否支持重…...

Linux系统下的性能分析命令

在 Linux 系统下&#xff0c;有许多用于性能分析和调试的命令和工具&#xff0c;可以帮助您识别系统瓶颈、优化性能以及调查问题。本文将介绍在性能分析过程中&#xff0c;可能使用到的一些命令。 以下是一些常用的性能分析命令和工具汇总&#xff1a; 命令功能简述top用于实…...

第十三课:QtCmd 命令行终端应用程序开发

功能描述&#xff1a;开发一个类似于 Windows 命令行提示符或 Linux 命令行终端的应用程序 一、最终演示效果 QtCmd 不是因为它是 Qt 的组件&#xff0c;而是采用 Qt 开发了一个类似 Windows 命令提示符或者 Linux 命令行终端的应用程序&#xff0c;故取名为 QtCmd。 上述演示…...

Jmeter进阶使用:BeanShell实现接口前置和后置操作

一、背景 我们使用Jmeter做压力测试或者接口测试时&#xff0c;除了最简单的直接对接口发起请求&#xff0c;很多时候需要对接口进行一些前置操作&#xff1a;比如提前生成测试数据&#xff0c;以及一些后置操作&#xff1a;比如提取接口响应内容中的某个字段的值。举个最常用…...

【知识分享】高防服务器的防御机制

【知识分享】高防服务器的防御机制 易受到攻击的网站选择接入高防服务更安全&#xff0c;大家对于这个都清楚!但是对于高防服务如何实现防御来保障安全的&#xff0c;又了解多少呢?今天壹基比小源&#xff08;贰伍壹叁壹叁壹贰玖捌&#xff09;就来说说高防服务实现防御的常规…...

内网穿透-外远程连接中的RabbitMQ服务

文章目录 前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道 4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 RabbitMQ是一个在 AMQP(高级消息队列协议)基…...

驱动DAY4 字符设备驱动分步注册和ioctl函数点亮LED灯

头文件 #ifndef __HEAD_H__ #define __HEAD_H__ typedef struct{unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int ODR; }gpio_t; #define PHY_LED1_ADDR 0X50006000 #define PHY_LED2_ADDR 0X50007000 #d…...

Python爬虫——scrapy_当当网图书管道封装

创建爬虫项目 srcapy startproject scrapy_dangdang进入到spider文件里创建爬虫文件&#xff08;这里爬取的是青春文学&#xff0c;仙侠玄幻分类&#xff09; srcapy genspider dang http://category.dangdang.com/cp01.01.07.00.00.00.html获取图片、名字和价格 # 所有的se…...

Linux下如何修改CPU 电源工作模式

最近处理一起历史遗留问题&#xff0c;感觉很爽。 现象&#xff1a; 背景&#xff1a;设备采用ARM&#xff0c;即rk3568处理器&#xff0c;采用Linux系统&#xff1b;主要用于视觉后端处理 现象&#xff1a;当软件运行一段时间&#xff0c;大概1个小时&#xff08;也不是很固定…...

Effective C++学习笔记(8)

目录 条款49&#xff1a;了解new-handler的行为条款50&#xff1a;了解new和delete的合理替换时机条款51&#xff1a;编写new和delete时需固守常规条款52&#xff1a;写了placement new也要写placement delete条款53&#xff1a;不要轻忽编译器的警告条款54&#xff1a;让自己熟…...

学校如何公布录取情况表?这个不用技术的方法,小白老师都能轻松制作

作为一名教师&#xff0c;我深切了解学生和家长们对录取情况的关注和重视。为了满足他们的需求&#xff0c;我们学校一直致力于改进公布录取情况的方式和效果。在本篇文章中&#xff0c;我将向您介绍我们学校独特的录取查询系统&#xff0c;并分享我们选择这种方式的原因。 我…...

Chart GPT免费可用地址共享资源

GPT4.0&#xff1a; https://gpt4e.ninvfeng.xyz github:https://github.com/ninvfeng/chatgpt4 WeUseAi&#xff1a;https://chatb.weuseai.pro AI.LS&#xff1a;https://n7.gpt03.xyz ChatX (iOS/macOS应用)&#xff1a;https://itunes.apple.com/app/id6446304087 ch…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...