Co jest najlepszą odpowiedzią na znalezienie maksymalną kwotę możliwego w tablicy

Question

Pytanie brzmi:

Znajdź maksymalną kwotę możliwego w tablicy liczb całkowitych dodatnich, wybierając elementy w taki sposób, że żadne dwa elementy są obok do siebie nawzajem.

jest odpowiedź tak: ale to, co jest najlepszą odpowiedzią na to pytanie

Niech oznaczają macierz przez „t” i indeksu to od 0. Niech f będzie funkcja tak że f (k) = maksymalna suma w podskali [0..k] z warunkami problemu. Teraz za pomocą programowania dynamicznego:

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

Z góry dzięki.

Answer 1

Proponowane rozwiązanie to good one.

Podobne podejście (strona 7 here):

Let m[i] być maksymalna suma dowolnej subarray który kończy na elemencie a[i] .Następnie m[i] jest po prostu max(a[i], m[i-1]+a[i]).

To O(n).

i nie można się niczego poniżej O(n) jak trzeba odwiedzić każdy element tablicy co najmniej raz, aby obliczyć wynik.

Answer 2

Myślę, że to już jest najlepsza odpowiedź.
Ponieważ potrzebujesz O (n) do odczytu danych.
Algorytm O (n) jest najszybszy w notacji big-O.

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