返回信息流有一个数组，长度为N。现在要在这个数组中取出K个数，要满足以下要求：
1、这K个数的和最大
2、这K个数中相邻的两个数的序号的差不能超过M（可以假设一个数）
如果没有条件2的话，一个堆排序就好了，前K大的数的和也一定是最大的。
现在加入了条件2，我就不知道怎么做了。哪位大神有思路？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91064同步于 2016/9/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
带条件的排序问题
akhyx
2016/9/16镜像同步15 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 akhyx 的大作中提到: 】
: 有一个数组，长度为N，取值范围为1-10000。现在要在这个数组中取出K个数，要满足一下要求：
: 1、这K个数中相邻的两个数的差不能超过M（可以假设一个数）
: 2、这K个数的和最大
: ...................
条件1什么意思？相邻且最大不是取最大的K个吗？
表达有误，在取出和最大的K个数，但是这k个数中相邻两个数的序号差值不能超过M。假如说K为2，M为3，那么a[0]和a[6]就不满足条件1。
【 在 dxy1 (【意涵团】dxy) 的大作中提到: 】
: 条件1什么意思？相邻且最大不是取最大的K个吗？
【 在 akhyx 的大作中提到: 】
: 表达有误，在取出和最大的K个数，但是这k个数中相邻两个数的序号差值不能超过M。假如说K为2，M为3，那么a[0]和a[6]就不满足条件1。
直接排序取前K个不就是最大吗？符合条件啊？还是没看懂条件1的作用
这样，假如这个数组为 6 1 2 3 4 5
现在要取最大的K=2个数，且这K个数中相邻的两个数的下标差值不能超过M=2。
如果直接取前K个最大的，很显然取出的是6和5，但是这两个数的下标为0和5，不满足条件“这K个数中相邻的两个数的下标差值不能超过M=2”
正确答案应该是4和5
能明白我想表达的意思了么？
【 在 dxy1 的大作中提到: 】
: 直接排序取前K个不就是最大吗？符合条件啊？还是没看懂条件1的作用
动态规划？
dp[i]表示的以符合必须以nums[i]为结尾的k长度的数列的要求的所有数列中，最长的那个数列的和。
然后从长度1开始遍历到k，所需要的时间复杂度和空间复杂度分别是O(N*K*M)和O(N)（两个dp数组交替）.
写个程序，没有测试样例也就没有试过是不是对的。
```
func sort(nums []int, k,m int) int{
dp,tmp := make([]int,len(nums)),make([]int,len(nums))
sum := -65535
for i:=0;i<len(nums);i++{
dp[i] = nums[i]
}
for l:=2;l<=k;l++{
for i:=l-1;i<len(nums);i++{
max := -65535
for j:=i-1;j>=i-m;j--{
if dp[j] >max{
max = dp[j]
}
}
tmp[i] = nums[i]+ max
}
copy(dp,tmp)
}
for i :=k-1;i<len(dp);i++{
if sum < dp[i]{
sum = dp[i]
}
}
return sum
}
```
【 在 NachtZ 的大作中提到: 】
: 动态规划？
: dp[i]表示的以nums[i]为结尾的所能得到的指定长度的数列的最大的和。
: 然后从长度1开始遍历到k，所需要的时间复杂度和空间复杂度分别是O(N*K*M)和O(N)（两个dp数组交替）.
应该是这样，跟0-1背包挺像啊
额，能否再详细点？我对算法这方面的知识比较差，听不懂[ema1]
【 在 NachtZ 的大作中提到: 】
: 动态规划？
: dp[i]表示的以nums[i]为结尾的所能得到的指定长度的数列的最大的和。
: 然后从长度1开始遍历到k，所需要的时间复杂度和空间复杂度分别是O(N*K*M)和O(N)（两个dp数组交替）.
写了个程序，编辑在我那个楼里面了。你要是不知道算法的话，我再想办法讲得详细点。[ema1]原本想讲得详细点发现自己讲不清楚就写个代码了。
【 在 akhyx 的大作中提到: 】
: 额，能否再详细点？我对算法这方面的知识比较差，听不懂