Skip to content

14265: 【原4265】手把手教你写前缀和

题目

题目描述

author: Guo Linsong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4265

Description

本来这道题目应该是这样:

请按照字典序顺序输出所有助教的名字。

身为一个不靠谱助教,今天手把手教同学们写前缀和。

前缀和可以简单理解为数列的前N项和。有N个的正整数放到数组A里,现在有一个新的数组B,也就是我们所说的前缀和数组,B数组的第i个数B[i]是原数组A第1个数到第i个数的和,也就是:

i=1时,B[1]=A[1].

i>1时,B[i]=A[1]+...+A[i]=B[i-1]+A[i].

这可以用一段很简洁的代码实现:

B[1]=A[1];

for(int i = 2; i <= N; ++i) B[i] = B[i - 1] + A[i];

这样,我们就可以很快得到一个区间[l,r]内所有数字的和A[l]+...+A[r]=B[r]-B[l-1].

下面才是真正的题目:

给定一个长度为N的数组A。

有M次询问,每次询问给定K,求出所有长度为K的区间的和的最大值。

比如,在样例中,该数组为[2,4,3,5,1].

有3次询问:

第一次询问K=1,长度为1的区间有[2],[4],[3],[5]和[1],最大值为5.

第一次询问K=3,长度为3的区间有[2,4,3],[4,3,5]和[3,5,1],最大值为4+3+5=12.

第一次询问K=5,长度为5的区间只有[2,4,3,5,1],最大值为2+4+3+5+1=15.

Input Format

第一行两个整数N,M.

第二行N个整数,表示数组A.

接下来有M行,每行1个整数,分别表示每次询问的K.

0<N<=10000.

0<M<=1000.

0<A[i]<=10000.

Output Format

M行,每行一个整数,表示一次询问的答案。

Sample Input

5 3
2 4 3 5 1
1
3
5

Sample Output

5
12
15

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!