algorithm - 寻找一组非相邻子数组的有效算法，使其总和最大化

Question

我在一个编程竞赛网站上遇到了这个问题，并尝试了几天不同的东西，但它们似乎都不够有效。

问题是：给定一个大整数数组和一个数字 k。目标是将数组划分为子数组，每个子数组包含不超过 k 个元素，使得所有子数组中所有元素的总和最大。另一个条件是这些子阵列中没有一个可以彼此相邻。换句话说，我们必须从原始数组中删除一些项。

它困扰了我一段时间，想听听您对解决这个问题的看法。

Answer 1

动态编程应该可以解决问题。简短的解释为什么：

易受动态规划影响的问题的关键特性是问题的最优解（这里：整个数组）总是可以表示为子问题（这里：两个子数组）的两个最优解的组合。并非每个拆分都需要有此属性 - 对于任何最佳解决方案，存在一个这样的拆分就足够了。

显然，如果您在数组之间拆分最优解（在已删除的元素上），那么子解在两个子数组中都是最优的。

算法：

依次尝试数组中的每个元素作为拆分元素，寻找产生最佳结果的元素。递归解决数组的两个部分的问题（当子数组不超过 时，递归停止k）。记忆解决方案以避免指数时间（递归显然会多次尝试相同的子数组。）

Answer 2

这不是一个解决方案，而是一个线索。

考虑解决以下问题：

从数组 X 中选择元素的一个子集，使得它们都不相邻并且它们的总和最大。

现在，上述问题是您的问题的一个特例，其中 K=1。想想如何将解决方案扩展到一般情况。如果您不知道如何解决更简单的情况，请告诉我。

Answer 3

我没有时间解释为什么会这样，应该是公认的答案：

def maxK(a, k): 
    states = k+1
    myList = [0 for i in range(states)]
    for i in range(0, len(a)): 
        maxV = max (myList)
        myList = [a[i] + j for j in myList]
        myList[(states-i) % k] = maxV  
    return max(myList) 

这也适用于负数。size(a)这在时间上是线性的k。我使用的语言是 Python，因为在这个级别上它可以像伪代码一样被阅读。