链接：https://ac.nowcoder.com/acm/problem/15553来源：牛客网 题目描述今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续
展开全文
NC15553 题意 给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？ 思路 前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。扫一遍要选的第一个区间，扫的过程如果左右还有
展开全文
Solution 由题意可知需要求两段不连续区间，使和最大。 区间求和问题可以想到一个常用算法：前缀和。区间 的和可以用 方便地求出。 预处理序列的前缀和后，如何得知某个位置之前和之后的和最大的区间呢？我们可以使用线性 求得。设 表示位置 之前的最大区间和， 表示位置 之后的最大区间和。
展开全文
首先声明一下，线段树做法对于本题而言无论是复杂度还是代码长度都劣于前缀和+dp做法。笔者也已经写了前缀和dp的题解：https://blog.nowcoder.net/n/1042c69bd06d40b98f69daf8f708b28b之所以写线段树做法，一是因为自己的数据结构很弱，需要练习（本题的
展开全文
题意 有 个数选两个长度为 的不相交区间，使得他们的和尽量大，求最大和。 分析 我们可以固定一个区间，然后来找另一个区间。记 为 的前缀和在这道题中，我们枚举 ，然后固定右边的区间 ，右边的贡献为 那么，现在就是在 中找长度为 的连续区间的和的最小值。那么我们设 表示 中长度为 的
展开全文
Update：线段树题解已更新：https://blog.nowcoder.net/n/7c67622afee94322af471bf99ff6ed6b 计 为 区间内，所有的 这样的区间中，数之和的最大值。那么只要遍历一遍，当左区间取 时，右区间的最大值可以 读取，即 。所有以上计算均
展开全文
Statement 今天qwb要参加一个数学考试，这套试卷一共有道题，每道题qwb能获得的分数为，qwb并不打算把这些题全做完，他想选总共道题来做，并且期望他能获得的分数尽可能的大，他准备选个不连续的长度为的区间，即。其中有。 Solution 把题意简单点说：将一个数组分成两个长度均为且不相交
展开全文
戳我传送 题意： 思路 求两个不连续的区间的最大和，很容易想到前缀和，[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点，另一个指针枚举右区间的起点，两层循环复杂度 （n^2）,应该会超时。枚举右区间的起点时，可以发现左区间的起点不需要从1开始找，此时的
展开全文
题意
找到两个不连续且长度为k的序列，使这两个序列和最大。
思路
用前缀和记录下前i个元素的和，然后从前往后遍历，依次记录当前序列和最大的值（ma），以及更新两个序列和的最大值（ans）。
可以很容易想到ma = max(ma, a[i] - a[i - k]), ans = max(ans,
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
