algorithm - 如何找到算法 : given an array of integers, 整数子集的最大总和是多少

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(含)。 (由于这完全是一个学习练习，如果整数范围从 -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 个元素的数组任务和 N-2第一要素。如果N = 0答案是0如果N = 1答案是A[1] .天气晴朗。对于 N >= 2我们有两种不同的方式:

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

2. 不要使用元素 A[N] , 那么答案就是F[N-1] (因为我们可以使用 A[N-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 - 使用第一、第三元素

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

答案是F[4] = 22 .