解题思路

设序列为 $b_1,b_2,\dots,b_m$ ，片段长度为 $t$ 。需要考察的片段一共有 $m-t+1$ 个，第 $j$ 个片段是 $b_j,b_{j+1},\dots,b_{j+t-1}$ （下标从 $1$ 计），答案是这些片段元素和的最大值，以及取到该值的片段个数。
相邻两个片段只相差一项：右端新进入一项，左端离开一项。因此用滑动窗口维护当前片段和，每次更新只要 $O(1)$ 。
先算出最左边那个片段的和，把它当作当前最大值，次数记为 $1$ 。窗口每向右走一步，若新和严格更大，就更新最大值并把次数改回 $1$ ；若新和恰好等于最大值，次数加 $1$ 。
元素可为负，片段和就是代数和，不能把负数改成 $0$ 。当 $t=m$ 时只有一个片段，循环体不会执行，答案就是整段之和与次数 $1$ 。所有项都为负时，最大值仍是这些定长片段里最大的那个和。
$m$ 最大为 $2 \times 10^5$ ，单项绝对值最大为 $10^9$ ，片段和最大约为 $2 \times 10^{14}$ ，累加时使用 $64$ 位整数。

复杂度分析

小月手头已有一串整数 $b_1,b_2,\dots,b_m$ ，另外还给定了正整数 $t$ 。她需要查看每一个由连续 $t$ 项组成的片段，先确定这些片段里元素相加后的最大结果，再清点有多少个片段能得到这个结果。

首行两个整数是 $m$ 与 $t$ （ $1 \le t \le m \le 2 \times 10^5$ ）， $m$ 为整数个数， $t$ 为片段所含项数。

下一行有 $m$ 个整数 $b_1,b_2,\dots,b_m$ （ $-10^9 \le b_j \le 10^9$ ），按从左到右的顺序给出每一项。

同一行输出两个整数：左边是片段元素相加的最大结果，右边是得到该结果的片段个数。

输入

6 3
2 -3 8 1 -4 5

输出

7 1

说明

长度为 $3$ 的相邻片段依次是 $[2,-3,8]$ 、 $[-3,8,1]$ 、 $[8,1,-4]$ 、 $[1,-4,5]$ ，元素之和依次为 $7$ 、 $6$ 、 $5$ 、 $2$ 。最大结果是 $7$ ，只有 $1$ 段达到。

输入

5 2
4 -1 4 -1 4

输出

3 4

说明

长度为 $2$ 的四段之和都是 $3$ ，所以最大结果是 $3$ ，段数是 $4$ 。

输入

4 1
-5 -2 -9 -2

输出

-2 2

说明

片段只含 $1$ 项时，结果就是各项本身。这里最大的一项是 $-2$ ，它出现了 $2$ 次。

选择提交后点击「开始AI分析」