在一个数组中找到可能的最大和的最佳答案是什么？

Question

问题是：

通过选择元素的方式，在正整数数组中找到可能的最大总和，使得没有两个元素相邻。

有一个答案如下： 但对于这个问题，什么是最好的答案呢？

让我们用“t”表示数组并从0开始索引。设f是一个函数，使得 f(k)=在满足问题条件的[0..k]子数组中的最大和。 现在使用动态规划：

f(0) = t[0]
f(1) = max{ t[0], t[1] }
f(k) = max{ f(k-2) + t[k], f(k-1) } if k >= 2

If the array has n elements we need f(n-1).

Thanks in advance.

- Elnaz

Answer 1

我认为这已经是最好的答案了。
因为读取数据需要 O(n) 的时间复杂度。
在大O符号表示法中，O(n) 算法是最快的。

- cloudygoose

---

上述算法不是O(n)。我的算法分析能力今晚不强，但上述算法至少是O(n lg n)或O(n^2)。 - Li-aung Yip

我不明白你的意思。如果你将f(i)存储在数组f[]中，那么你只需要运行计算f[1]..f[n]一次即可。 - cloudygoose

啊，你说得对。不用理我。 - Li-aung Yip

Answer 2

你提出的解决方案很不错。

类似的方法（在此第7页）：

令m[i]为以元素a[i]结尾的任何子数组的最大总和。那么m[i]就是max(a[i], m[i-1]+a[i])。

这是一个O(n)算法。

你无法得到比O(n)更低的复杂度，因为必须至少访问一次数组中的每个项来计算结果。

- Tejas Patil

Answer 3

public static int maxSum(int[] A){
    return maxSum(A,0,1);
}
private static int maxSum(int[] A, int x, int y){
    int c =0, d=0;
    if(x<A.length){
        c = A[x]+maxSum(A,x+2,x+3);
    }
    if(y<A.length){
        d = A[y]+maxSum(A,y+2,y+3);
    }
    return c>d?c:d;
}

- kasavbere