百度笔试题2

输入一个程度为N的整数序列a1,a2,...,an，你的任务是恰好选择两个非空子段，子段是指原序列中的连续语段，这两个子段不能有重复部分，且他们之间相隔必须大于K，例如选择[1,5]和[8,10]K=2时合法，但在K>=3就不合法了，你需要最大化你选择的这两个字段内的整数之和，请求出最大值

输入

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

这个问题可以使用动态规划和前缀和来解决。我们可以遍历所有可能的第一个子段和第二个子段，并保证这两个子段的距离满足 KKK 的条件，最后求出最大化的两个子段之和。

思路解析：

1. 前缀和数组： 为了方便快速计算某个子段的和，可以先预处理一个前缀和数组。前缀和数组 prefix_sum[i] 表示从序列开头到位置 iii 的所有元素的和，这样子段 [l,r][l, r][l,r] 的和就可以通过公式 prefix_sum[r] - prefix_sum[l-1] 快速计算。

2. 动态规划： 用动态规划来保存到每个位置为止能选取的最大子段和。我们需要两个动态规划数组：

   
   
   • dp1[i]：表示以第 iii 位置结尾的最大子段和。

   • dp2[i]：表示从第 iii 位置开始，并且满足与前一个子段的距离大于 KKK 的第二个子段和。
     3. 状态转移：

   • 我们可以先计算 dp1[i]，然后再从前往后依次遍历序列，对于每个 iii，我们计算以 iii 结尾的子段和。

   • 然后遍历可能的第二个子段，确保第二个子段起始位置满足与第一个子段的间隔大于 KKK，记录可能的最大值。

具体步骤：

1. 先计算前缀和。
2. 用双循环遍历所有可能的子段对。
3. 使用一个变量保存当前最大和。