问题化简

我们可以将问题化简为：选中两个下标$i,j$ 使得 $j - i > K$ 。然后在前缀$[1 , i]$ 和 后缀$[j,n]$ 内分别寻找两个子段使得和最大。

前缀/后缀中的最大子段和

现在我们需要在前缀$[1 , i]$ 中寻找最大子段和。那么根据【动态规划4】最大子段和 我们直接求解，答案为$max\{dp_1,dp_2,...,dp_i\}$

又由于这个下标 $i$ 是频繁变化的，所以我们需要对每个不同的 $i$ 都求解一遍答案。那么根据上节课所学的知识，我们可以预处理出$dp$数组的前缀最大值数组。

本题为2024年10月15日百度机考原题

百度机考的介绍点击这里

题目内容

输入一个长度为$n$的整数序列$a_1,a_2,...a_n$。你的任务是恰好选择两个非空子段。子段是指原序列中的连续一段。这两个子段不能有重复部分，且他们之间相隔必须大于$K$。例如，选择子段[$1,5$]和[$8,10$]在$K=2$时合法，但是在$K≥3$时就不合法了。

你需要最大化你选择的这两个子段内的整数之和。请求出这个最大值。

输入描述

第一行输入一个正整数$T$，表示数据组数。

对于每一组数据，第一行输入两个整数$n,K$。第二行输入$n$个整数$a_1,a_2,...a_n$。

$1≤n≤10^5,-10^4≤a_i≤10^4,0≤k≤n-2,1≤T≤5$

输出描述

对于每一组数据，输出一行一个整数，表示答案。

样例1

输入

3
5 3
-1 1 2 3 -1
8 3
5 5 -1 -2 3 -1 2 -2
6 0
5 -1 5 0 -1 9

输出

-2
12
18

说明

第一组数据,只能选择[$1,1$]和[$5,5$]，这样答案就是$-2$。

第二组数据，可以选择[$1,2$]和[$7,7$]，这样答案就是$5+5+2=12$。

第三组数据,可以选择[$1,4$]和[$6,6$]，这样答案就是$5+(-1)+5+0+9=18$。