如何找到算法:给定一个整数数组，满足以下条件的整数子集的最大和是多少

Question

给定一个整数数组，使得该子集中的整数最初不相邻的整数子集的最大和是多少？

示例：

[3, 8, 4] => max sum is 8, since 8 > (3+4)
[12, 8, 9, 10] => max sum is 12 + 10 = 22, since this is greater than 12 + 9 and 8 + 10

我感兴趣的是找出做这件事的算法。方法论/思考过程=非常感谢。

编辑:整数范围从1到1000，包括1和1000。(因为这完全是一个学习练习，所以如果整数的范围从-1000到1000，我仍然有兴趣学习不同的方法。)

Answer 1

让您拥有数组A {Ai, 1 <= i <= n }

F(i) -子数组Aj { 1 <= j <= i }的最大和，然后

F(0) = 0 -空子数组

仅限F(1) = A(1)的第一个元素

F(i) = max(F(i-2) + A(i), F(i-1)) , 2 <= i <= n

F(n) -应答

C++实现：

int GetMaximumSubarraySum(const vector<int>& a)
{
    // note that vector a have 1-based index
    vector<int> v(a.size());
    v[0] = 0;
    v[1] = a[1];
    for(int i =2; i < a.size(); i++)
        v[i] = max(v[i-2] + a[i], v[i-1]);

    return v.back();
}

说明：

首先，主要思想是使用dynamic programming。我们尝试用N-1和N-2第一个元素数组的已知解来解决N个元素数组的问题。如果为N = 0，则答案为0；如果为N = 1，则答案为A[1]。清楚了。对于N >= 2，我们有两种不同的方式：

1. Use element A[N],那么答案是A[N] + F[N-2] (因为我们不能使用-1元素，而F[N-2]是子数组1..N-2的最佳解决方案，我们不关心是否使用F[N-2]元素，这只是子数组使用element A[N]的最佳解决方案，那么答案是F[N-1] (因为我们可以使用-1元素，F[N-1]是子数组1..N-1的最佳解决方案，此外，我们也不关心是否使用了F[N-1]元素。

所以我们需要得到这两种情况的最大值。为了解决这个问题，你需要按升序计算F[N]并记住答案。

让我们看看你的例子：

[12, 8, 9, 10]

F[0] = 0

F[1] = 12 -使用第一个元素

F[2] = max(F[0]+A[2], F[1]) = max(8, 12) = 12 -使用第一个元素

F[3] = max(F[1]+A[3], F[2]) = max(21, 12) = 21 -使用1-st，3-rd元素

F[4] = max(F[2]+A[4], F[3]) = max(22, 21) = 22 -使用第1、第4个元素

答案是F[4] = 22。

Answer 2

我所知道的唯一一致成功的思考过程是之前看过这个问题。看着你的问题，我的第一个想法是“我需要在一组相当简单的布尔约束下最大化一个和”。在Knuth Vol4A节7.1.4 Algorithm B Knuth中描述了如何解决这样的问题，只要约束可以表示为可管理大小的http://en.wikipedia.org/wiki/Binary_decision_diagram。如果您已经有了BDD包，那么只需构建一个描述特定约束的BDD，就可以解决这类问题。

我的第二个想法是注意到，在同一节的后面，Knuth展示了BDD和布尔逻辑的线性网络之间的联系。鉴于此，应该有一个易于处理的动态编程解决方案来解决您的问题。如果你正在寻找一种通用的学习方法，动态编程是一个很好的选择。在这种情况下，它似乎导致了一个与Ivan Benko提出的算法非常相似的算法，尽管他似乎是在一个假设下工作的-由您的示例数据支持-整数都是>= 0，并且它可以使用更多的if语句来处理一般的整数。

Answer 3

递归思考:最好的结果是最大值-使用第一个元素(递归分支中的第一个)或不使用它

最佳(I)= Max(Ai +最佳(i+ 2)，最佳(i+ 1))