PTA 7-1 最大子列和问题
给定K个整数组成的序列{ N1, N2, ..., NK },“连续子列”被定义为{ Ni, Ni+1, ..., Nj },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:
- 数据1:与样例等价,测试基本正确性;
- 数据2:102个随机整数;
- 数据3:103个随机整数;
- 数据4:104个随机整数;
- 数据5:105个随机整数;
输入格式:
输入第1行给出正整数K (≤100000);第2行给出K个整数,其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。
输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20
示例代码:
暴力解:
#include<stdio.h>
int main()
{int n;int a[100000];scanf("%d",&n);int i=0,j=0,k=0,sum=0,maxsum=0;for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0;i<n;i++)//i是子列左端的位置{for(j=i;j<n;j++)//j是子列右端的位置{sum=0;for(k=i;k<=j;k++)//子列和 从a[i]加到a[j]{sum=sum+a[k];}if(sum>maxsum)//判断当前子列和是否比最大子列和大 若是 则更新{maxsum=sum;}}}printf("%d",maxsum);
}
超级无敌牛逼在线处理法:
#include<stdio.h>
int main()
{int n;int a[100000];scanf("%d",&n);int i=0,j=0,k=0,sum=0,maxsum=0;for(i=0;i<n;i++){scanf("%d",&a[i]);}for(j=0;j<n;j++){sum=sum+a[j];if(sum>maxsum){maxsum=sum;}else if(sum<0){sum=0;}}printf("%d",maxsum);
}
补充说明:算法题比函数题难的不是一点啊。
暴力解的大致思路就是从一个数字到n个数字,求这些子列的和,挑一个最大的出来。暴力解的数据偏大的三个测试点运行超时。我们学校数据结构与算法用的不是浙大的书,陈越老师讲的最方便的是上边这种算法,时间复杂度只有O(n)。算法的思路是当前如果求出的sum大于最大值,那么就需要更新最大值,这一步相信大家都能理解,关键在后面当sum小于0时,就要将sum置为0,因为sum小于0时,不管后面是什么数,加上这个sum都只会更小,所以需要将sum置为0,从后一个元素重新计算子列和,陈越老师称其为在线处理法,不得不说真的秒啊。
相关文章:
PTA 7-1 最大子列和问题
给定K个整数组成的序列{ N1, N2, ..., NK },“连续子列”被定义为{ Ni, Ni1, ..., Nj },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4,…...

JAVA实现向Word模板中插入Base64图片和数据信息
目录 需求一、准备模板文件二、引入Poi-tl、Apache POI依赖三、创建实体类(用于保存向Word中写入的数据)四、实现Service接口五、Controller层实现 需求 在服务端提前准备好Word模板文件,并在用户请求接口时服务端动态获取图片。数据等信息插…...

深入浅出关于go web的请求路由
文章目录 前言一、是否一定要用框架来使用路由?二、httprouter2.1 httprouter介绍2.2 httprouter原理2.3 路由冲突情况 三、gin中的路由四、hertz中的路由总结 前言 最近重新接触Go语言以及对应框架,想借此机会深入下对应部分。 并分享一下最近学的过程…...

HarmonyOS—开发环境诊断的功能
为了大家开发应用/服务的良好体验,DevEco Studio提供了开发环境诊断的功能,帮助大家识别开发环境是否完备。可以在欢迎界面单击Help > Diagnose Development Environment进行诊断。如果已经打开了工程开发界面,也可以在菜单栏单击Help >…...

Golang个人web框架开发-学习流程
Golang-个人web框架 github仓库创建github仓库 web框架学习开发周期第一阶段--了解第一阶段思考小结 第二阶段第三阶段 github仓库 github地址:ameamezhou/golang-web-frame 后续还将继续学习更新 创建github仓库 设置免密登录 ssh-keygen 一路回车就OK 上面有告…...
java面试题(23):Spring Bean如何保证并发安全
1 问题分析 我们知道默认情况下,Spring中的Bean是单例的,所以在多线程并发访问的时候,有可能会出现线程安全问题。 2 解决方案 有几个方面的解决思路: 我们可以设置Bean的作用域设置为原型(prototype)&a…...

HarmonyOS【应用服务开发】在模块中添加Ability
Ability是应用/服务所具备的能力的抽象,一个Module可以包含一个或多个Ability。应用/服务先后提供了两种应用模型: FA(Feature Ability)模型: API 7开始支持的模型,已经不再主推。Stage模型:AP…...
根据屏幕尺寸设置html根字号fontSize大小并刷新
<script> // rem等比适配配置文件 // 基准大小 const baseSize 16 // 设置 rem 函数 function setRem() {// 当前页面宽度相对于 1920宽的缩放比例,可根据自己需要修改。const scale document.documentElement.clientWidth / 1920console.log(document.docu…...
Flutter 中的 InteractiveViewer:轻松实现交互性
在Flutter中,为了创建具有交互性的用户界面,我们通常需要使用各种手势检测和动画。然而,Flutter提供了一个强大而简便的小部件,即InteractiveViewer,它可以帮助我们轻松实现拖动、缩放和其他手势交互效果。本文将介绍I…...

UE4 添加按键输入事件 并在蓝图中使用按键输入节点
绑定按键 选择Edit/ProjectSettings/Engine/Input 在bindings中可以选择添加ActionMappings或则AxisMappings ActionMappings:按键事件,有按下和抬起两个事件,需要分别用两个键触发AxisMappings:输入事件,返回值为float,对于键盘…...
Go 语言命名规范:清晰、简洁、一致
Go 语言命名规范:清晰、简洁、一致 Go 语言是一门注重简洁和一致性的编程语言,良好的命名规范是代码可读性和维护性的关键因素之一。在本篇博客中,我们将深入探讨 Go 语言的命名规范,包括标识符、包名、常量、变量、函数等各个方…...
代码随想录训练营第三十期|第十天|栈与队列part01|理论基础● 232.用栈实现队列● 225. 用队列实现栈
232. 用栈实现队列 - 力扣(LeetCode) class MyQueue {Stack<Integer> in;Stack<Integer> out;public MyQueue() {in new Stack<>();out new Stack<>();}public void push(int x) {in.push(x);}public int pop() {move();retu…...

Backtrader 文档学习-Indicators混合时间框架
Backtrader 文档学习-Indicators混合时间周期 1.不同时间周期 如果数据源在Cerebro引擎中具有不同的时间范围和不同的长度,指示器将会终止。 比如:data0是日线,data1是月线 。 pivotpoint btind.PivotPoint(self.data1) sellsignal self…...

网络攻击与检测防御:维护数字安全的关键挑战
随着数字化时代的深入,网络攻击已成为企业和个人面临的严峻挑战之一。本文将深入探讨不同类型的网络攻击,以及有效的检测和防御策略,以确保网络系统的安全性和稳定性。 1. 常见网络攻击类型: DDoS 攻击:分布式拒绝服…...

使用 Vector 在 Kubernetes 中收集日志
多年来,我们一直在使用 Vector 在我们的 Kubernetes 平台中收集日志,并成功地将其应用于生产中以满足各种客户的需求,并且非常享受这种体验。因此,我想与更大的社区分享它,以便更多的 K8s 运营商可以看到潜力并考虑他们…...
ardupilot开发 --- 固件定制(OEM) 篇
0. 前言 固件功能定制OEM Customization: 原厂设备制造商OEM(Original Equipment Manufacturer)、代工功能勾选参数预设固件名称自定义 1. 基于某个飞控硬件来定制自己的飞控产品 可以自定义的包括:固件名称、预设参数、lua脚本…...
爬虫代理IP在电商行业的应用
随着互联网的快速发展,电商行业已经成为人们购物的主要渠道之一。在电商行业中,数据分析和挖掘至关重要。爬虫代理IP作为一种能够提供大量模拟请求和收集数据的工具,被广泛应用于电商行业。下面介绍爬虫代理IP在电商行业中的应用。 1、保护隐…...
Vue配置语法检查及关闭语法检查的说明
1. 第一种方式://eslint-disable-next-line 2. 第二种方式:/*eslint-disable*/ 3. 第三种方式:vue.config.js中配置 ,具体配置如下: const { defineConfig } require(vue/cli-service)module.exports defineConfig…...

【Linux】yum
个人主页 : zxctsclrjjjcph 文章封面来自:艺术家–贤海林 如有转载请先通知 yum 1. 什么是yum?2. Linux系统(Centos)的生态3. yum的相关操作4. yum的本地配置5. 如何安装软件 1. 什么是yum? yum是一个软件下载安装的一个客户端&a…...
安装sftpgo
1.下载安装包;选择自己需要的cpu架构和操作系统的版本 https://github.com/drakkan/sftpgo/releases/tag/v2.5.6推荐使用版本下载地址 https://github.com/drakkan/sftpgo/releases/download/v2.5.6/sftpgo_v2.5.6_linux_x86_64.tar.xz2.解压文件到某个文件夹,根据需要修改配…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...

【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...