问题化简
我们可以将问题化简为：选中两个下标i,j 使得 j−i>K 。然后在前缀[1,i] 和 后缀[j,n] 内分别寻找两个子段使得和最大。
前缀/后缀中的最大子段和
现在我们需要在前缀[1,i] 中寻找最大子段和。那么根据【动态规划4】最大子段和 我们直接求解，答案为max{dp1,dp2,...,dpi}
又由于这个下标 i 是频繁变化的，所以我们需要对每个不同的 i 都求解一遍答案。那么根据上节课所学的知识，我们可以预处理出dp数组的前缀最大值数组。
P3904.距离为k的两段最大子段和
题目内容
输入一个长度为n的整数序列a1,a2,...an。你的任务是恰好选择两个非空子段。子段是指原序列中的连续一段。这两个子段不能有重复部分，且他们之间相隔必须大于K。例如，选择子段[1,5]和[8,10]在K=2时合法，但是在K≥3时就不合法了。
你需要最大化你选择的这两个子段内的整数之和。请求出这个最大值。
输入描述
第一行输入一个正整数T，表示数据组数。
对于每一组数据，第一行输入两个整数n,K。第二行输入n个整数a1,a2,...an。
1≤n≤105,−104≤ai≤104,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。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
