最大连续和
【问题描述】
对于一个具有n个元素的整型数组 a,求具有最大连续和的子数组(最少具有一个元素)。
【输入形式】
输入的第一行为一个整数 n,接下来的一行为 n 个整数,表示数组的元素。
【输出形式】
输出具有最大连续和的子数组的起始编号和结束编号(数组编号为0~n-1)。
【样例输入】
8
3 -5 1 5 -4 12 0 -1
【样例输出】
2 5
解题思路
题目要求:寻找给定数组中具有最大连续和的子数组的起始和结束位置
-
从命令行读取数组的长度和元素:n,a[n]
-
初始化变量:
-
int maxSoFar=a[0]; 迄今为止最大连续子数组的和
-
int maxEndingHere=a[0]; 以当前元素结尾的最大连续子数组的和
-
start、end:起始位置、结尾位置
-
s:临时变量,用于更新最大连续子数组和的开始位置
-
-
遍历数组:i从1开始遍历(因为第一个元素已用于初始化)
-
对于每个元素,判断maxEndHere + a[i] < a[i],即判断将其加入到当前子数组中是否会使得子数组的和增大。
-
如果直接使用当前元素的值比加上之前的maxEndHere还大,说明从当前元素开始的子数组可能会有更大的和,于是更新maxEndHere为当前元素的值,并更新起始位置
s。 -
否则,maxEndHere加上当前元素,继续向下遍历
-
-
判断maxEndHere > maxSoFar,即判断是否找到了一个更大的子数组和。如果是,更新maxSoFar,更新起始和结束位置的start和end。
-
-
输出起始和结束位置的start和end,中间空格用“”双引号。
Java代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//命令行键入n个整数int n = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}//变量初始化int maxSoFar = a[0], maxEndHere = a[0]; //maxSoFar:迄今为止最大的子数组和;maxEndHere:以当前元素结尾的最大字数组和int start = 0, end = 0; //最大子数组和的起始位置和结束位置int s = 0; //临时变量,用来记录以当前元素结尾的最大子数组和的起始位置//循环遍历判断for (int i = 1; i < n; i++) { //i从1开始是因为a[0]已经用于初始化if(maxEndHere + a[i] < a[i]){ //如果直接使用当前元素的值比加上之前的maxEndingHere还大,说明从当前元素开始的子数组可能会有更大的和maxEndHere = a[i]; //更新maxEndingHere为当前元素的值s = i; //记录下这个可能的新起始位置s}else{maxEndHere += a[i];}if(maxEndHere > maxSoFar){ //判断是否找到了一个更大的子数组和maxSoFar = maxEndHere; //是:更新maxSoFarstart = s; //更新记录最大子数组起始和结束位置的start和end。end = i;}}System.out.println(start + " " + end);scanner.close();}
}
相关文章:
最大连续和
【问题描述】 对于一个具有n个元素的整型数组 a,求具有最大连续和的子数组(最少具有一个元素)。 【输入形式】 输入的第一行为一个整数 n,接下来的一行为 n 个整数,表示数组的元素。 【输出形式】 输出具有最大连续和的…...
分布式系统事务一致性解决方案(基于事务消息)
参考:https://rocketmq.apache.org/zh/docs/featureBehavior/04transactionmessage/ 文章目录 概要错误的方案方案一:业务方自己实现方案二:RocketMQ 事务消息什么是事务消息事务消息处理流程事务消息生命周期使用限制使用示例使用建议 概要 …...
Unity Animation--动画剪辑
Unity Animation--动画剪辑 动画剪辑 动画剪辑是Unity动画系统的核心元素之一。Unity支持从外部来源导入动画,并提供创建动画剪辑的能力使用“动画”窗口在编辑器中从头开始。 外部来源的动画 从外部来源导入的动画剪辑可能包括: 人形动画 运动捕捉…...
如何将 redis 快速部署为 docker 容器?
部署 Redis 作为 Docker 容器是一种快速、灵活且可重复使用的方式,特别适合开发、测试和部署环境。本文将详细介绍如何将 Redis 部署为 Docker 容器,包括 Docker 安装、Redis 容器配置、数据持久化、网络设置等方面。 步骤 1:安装 Docker 首…...
iOS - Undefined symbols: 解决方法
Undefined symbols: 是让人苦恼的报错,如何知道是 哪个 symbols 不对呢? 今天探索到下面的方法: 1、点击导航上方 最右侧的按钮,查看历史报错 2、选中报错信息,右键选择 Expand All Transcripts 在出现的详细信息面…...
优化理论复习——(三)
本篇介绍无约束优化的问题,通过四种算法来进行求解的过程和思路,也是最优化方法中的最重要的一类问题。 无约束优化问题主要是通过迭代搜索算法来切结,比线性规划的计算量都小一点。 目录 无约束优化问题最优性条件最速下降法牛顿法共轭梯度…...
RK3568笔记二十四:基于Flask的网页监控系统
若该文为原创文章,转载请注明原文出处。 此实验参考 《鲁班猫监控检测》,原代码有点BUG,已经下载不了。2. 鲁班猫监控检测 — [野火]嵌入式AI应用开发实战指南—基于LubanCat-RK系列板卡 文档 (embedfire.com) 一、简介 记录简单的摄像头监…...
[Django 0-1] Core.Serializers 模块
Core.Serializers 模块 Django 序列化模块 模块结构 . ├── __init__.py ├── base.py ├── json.py ├── jsonl.py ├── python.py ├── pyyaml.py └── xml_serializer.py1 directory, 7 files自定义序列化器 通过继承django.core.serializers.base.Serial…...
鸿蒙内核源码分析(用栈方式篇) | 程序运行场地谁提供的
精读内核源码就绕不过汇编语言,鸿蒙内核有6个汇编文件,读不懂它们就真的很难理解以下问题. 1.系统调用是如何实现的? 2.CPU是如何切换任务和进程上下文的? 3.硬件中断是如何处理的? 4.main函数到底是怎么来的? 5.开机最开始发生了什么? 6.关机…...
Linux 进程间通信之匿名管道
💓博主CSDN主页:麻辣韭菜💓 ⏩专栏分类:Linux知识分享⏪ 🚚代码仓库:Linux代码练习🚚 🌹关注我🫵带你学习更多Linux知识 🔝 目录 前言 一. 进程间通信介绍 1.进程间通…...
数据结构与算法学习笔记六--数组和广义表(C语言)
目录 前言 1.数组 1.定义 2.初始化 3.销毁 4.取值 5.设置值 6.完整代码 前言 这篇博客主要介绍数据结构中的数组和广义表的用法。 1.数组 在数据结构中,数组是一种线性数据结构,它由一组连续的相同类型的元素组成,每个元素都有一个唯…...
图搜索算法详解
图搜索算法详解 摘要: 图搜索算法是解决路径规划和网络分析问题的关键技术。本文将详细介绍图搜索算法的基本概念、分类以及常见的算法,如广度优先搜索(BFS)、深度优先搜索(DFS)、A*搜索等。同时ÿ…...
安卓中常见的UI控件
TextView(文本视图)EditText(编辑文本)Button(按钮)ImageView(图像视图)ImageButton(图像按钮)CheckBox(复选框)RadioButtonÿ…...
基于Labelme的背部穴位关键点制作
一、穴位定位方法 穴位定位,自春秋时期以来,通过各代医学实践的继承与发展,形成了一套较为科学的定位体系。这套体系基于经络理论,采用“寸”作为测量单位,按照人体比例来进行精确的穴位定位,主要有依据体…...
go-mysql-transfer 同步数据到es
同步数据需要注意的事项 前提条件 1 要同步的mysql 表必须包含主键 2 mysql binlog 必须是row 模式 3 不支持程序运行过程中修改表结构 4 要赋予连接mysql 账号的权限 reload, replication super 权限 如果是root 权限则不需要 安装 go-mysql-transfer git clone…...
外包干了3天,技术就明显退步了。。。。。
先说一下自己的情况,本科生,19年通过校招进入广州某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...
将要上市的自动驾驶新书《自动驾驶系统开发》中摘录各章片段 1
以下摘录一些章节片段: 1. 概论 自动驾驶系统的认知中有一些模糊的地方,比如自动驾驶系统如何定义的问题,自动驾驶的研发为什么会有那么多的子模块,怎么才算自动驾驶落地等等。本章想先给读者一个概括介绍,了解自动驾…...
String、StringBuilder、StringBuffer之间的区别是什么?
在Java中,String、StringBuilder 和 StringBuffer 是处理字符串的三个类,其中 String 是不可变对象,而 StringBuilder 和 StringBuffer 是可变对象。这些类在字符串操作方面具有不同的特性和用途。 String String 类表示不可变的字符序列&a…...
docker系列8:容器卷挂载(上)
目录 传送门 从安装redis说起 什么是容器卷挂载 操作系统的挂载 日志文件一般是"首恶元凶" 挂载命令 容器卷挂载 卷挂载命令 启动时挂载 查看挂载卷信息 容器卷管理 查看卷列表 创建容器卷 具名挂载与匿名挂载 具名挂载 传送门 docker系列1ÿ…...
痉挛性斜颈患者自己做哪些运动对脖子好?
痉挛性斜颈(Dystonia)是一种罕见的神经系统疾病,其特点是颈部肌肉痉挛,导致头部姿势异常倾斜或扭曲。而在治疗痉挛性斜颈中,运动疗法是非常重要的一部分。下面将介绍一些痉挛性斜颈患者可以自己进行的运动,…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
