c - 找到数组中可能的最大和的最佳答案是什么

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).

提前致谢。

Answer 1

好吧，我认为这已经是最好的答案了。
因为您需要 O(n) 才能读取数据。
O(n) 算法在大 O 表示法中是最快的。

Answer 2

您提出的解决方案很好。

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

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

这是O(n).

并且您无法在下面得到任何东西，O(n)因为您必须至少访问一次数组的每个项目来计算结果。

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