c - 配列で可能な最大の合計を見つけるための最良の答えは何ですか

Question

質問は ：

2つの要素が隣接しないように要素を選択して、正の整数の配列で可能な最大の合計を見つけます。

このような答えがあります：しかし、この質問の最良の答えは何ですか

配列を「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) アルゴリズムは、big-O 表記で最速です。

Answer 2

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