如何找到算法:给定一个整数数组,整数子集的最大总和是多少

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();
}

说明:

首先,主要思想是使用动态编程.我们尝试使用已知的数组N-1和N-2第一个元素的答案来解决具有N元素的数组的任务.如果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 - 使用1-st,3-rd元素

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

答案是F[4] = 22.