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.length1 <= 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 ,返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[…...
PhpOffice/PhpSpreadsheet读取和写入Excel
PhpSpreadsheet是一个纯PHP编写的组件库,它使用现代PHP写法,代码质量和性能比PHPExcel高不少,完全可以替代PHPExcel(PHPExcel已不再维护)。使用PhpSpreadsheet可以轻松读取和写入Excel文档,支持Excel的所有…...
jenkins自动化部署Jenkinsfile文件配置
简介 使用jenkins部署时会读取项目中Jenkinsfile文件,文件配置不对会导致部署失败 文件内容 pipeline {agent anyparameters {string(name: project_name, defaultValue: xxx1, description: 项目jar名称)string(name: version, defaultValue: xxx2, description…...
【socket编程简述】TCP UDP 通信总结、TCP连接的三次握手、TCP断开的四次挥手
Socket:Socket被称做 套接字,是网络通信中的一种约定。 Socket编程的应用无处不在,我们平时用的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四维代码:AC三维代码: 题目描述 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中&#…...
杭电比赛总结
我们的队伍:team013 另外两队:team014、team015 今天是我第一次打杭电,发现杭电多数都是猜结论题 先给一下我们的提交数据 Submit TimeProblem IDTimeMemoryJudge Status4:59:59101115 MS1692 KWrong Answer4:59:55101115 MS1684 KWrong…...
dom靶场
靶场下载地址: 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?2. 如何声明、定义和创建一个struct?3. struct和其他数据类型(如数组、切片、map等)有什么区别?4. 如何访问struct字段?5. struct是否支持继承,是否支持重…...
Linux系统下的性能分析命令
在 Linux 系统下,有许多用于性能分析和调试的命令和工具,可以帮助您识别系统瓶颈、优化性能以及调查问题。本文将介绍在性能分析过程中,可能使用到的一些命令。 以下是一些常用的性能分析命令和工具汇总: 命令功能简述top用于实…...
第十三课:QtCmd 命令行终端应用程序开发
功能描述:开发一个类似于 Windows 命令行提示符或 Linux 命令行终端的应用程序 一、最终演示效果 QtCmd 不是因为它是 Qt 的组件,而是采用 Qt 开发了一个类似 Windows 命令提示符或者 Linux 命令行终端的应用程序,故取名为 QtCmd。 上述演示…...
Jmeter进阶使用:BeanShell实现接口前置和后置操作
一、背景 我们使用Jmeter做压力测试或者接口测试时,除了最简单的直接对接口发起请求,很多时候需要对接口进行一些前置操作:比如提前生成测试数据,以及一些后置操作:比如提取接口响应内容中的某个字段的值。举个最常用…...
【知识分享】高防服务器的防御机制
【知识分享】高防服务器的防御机制 易受到攻击的网站选择接入高防服务更安全,大家对于这个都清楚!但是对于高防服务如何实现防御来保障安全的,又了解多少呢?今天壹基比小源(贰伍壹叁壹叁壹贰玖捌)就来说说高防服务实现防御的常规…...
内网穿透-外远程连接中的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文件里创建爬虫文件(这里爬取的是青春文学,仙侠玄幻分类) srcapy genspider dang http://category.dangdang.com/cp01.01.07.00.00.00.html获取图片、名字和价格 # 所有的se…...
Linux下如何修改CPU 电源工作模式
最近处理一起历史遗留问题,感觉很爽。 现象: 背景:设备采用ARM,即rk3568处理器,采用Linux系统;主要用于视觉后端处理 现象:当软件运行一段时间,大概1个小时(也不是很固定…...
Effective C++学习笔记(8)
目录 条款49:了解new-handler的行为条款50:了解new和delete的合理替换时机条款51:编写new和delete时需固守常规条款52:写了placement new也要写placement delete条款53:不要轻忽编译器的警告条款54:让自己熟…...
学校如何公布录取情况表?这个不用技术的方法,小白老师都能轻松制作
作为一名教师,我深切了解学生和家长们对录取情况的关注和重视。为了满足他们的需求,我们学校一直致力于改进公布录取情况的方式和效果。在本篇文章中,我将向您介绍我们学校独特的录取查询系统,并分享我们选择这种方式的原因。 我…...
Chart GPT免费可用地址共享资源
GPT4.0: https://gpt4e.ninvfeng.xyz github:https://github.com/ninvfeng/chatgpt4 WeUseAi:https://chatb.weuseai.pro AI.LS:https://n7.gpt03.xyz ChatX (iOS/macOS应用):https://itunes.apple.com/app/id6446304087 ch…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
