子曰:“三人行,必有我师”。人越多,可请教的也越多。假设有 n 个人排成一列,每个人的知识值是一个整数,现在我们想要选取 k 个连续的人,使得这 k 个人的知识值之和最大,请你输出这个最大值。
输入包含 2 行:
输出为一个整数,为连续 k 个人的知识值之和的最大值
5 3 1 2 2 3 1
7
解法一:首先求出前缀和,再依次枚举 k 个人下标的起点,通过前缀和数组相减求出 k 个人的知识值之和。
解法二:可以采用“滑动窗口的方法”,首先计算前 k 个人的知识值之和,作为初始窗口,之后每次减去最左侧的值,在最右侧添加一个新的值,就可以依次得到第 2 \sim k + 1、3 \sim k + 2、4 \sim k + 3...... 个人的知识值之和,同时求最大值即可