¿Cuál es la mejor respuesta para la búsqueda de la máxima cantidad posible de una matriz

Question

La pregunta es:

Halla la suma máxima posible en una matriz de enteros positivos mediante la selección de los elementos de tal manera que no hay dos elementos están al lado el uno al otro.

hay una respuesta como esta: pero lo que es la mejor respuesta para esta pregunta

Vamos a denotar la matriz por "t" y el índice de 0. Sea f una función modo que f (k) = la suma máxima en el subarreglo [0..k] con las condiciones del problema. Ahora usa la programación dinámica:

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

Gracias de antemano.

Answer 1

La solución que ha propuesto es good one.

enfoque similar (página 7 here):

Let m[i] sea la suma máxima de cualquier submatriz que termina en el elemento a[i] .A continuación m[i] es simplemente max(a[i], m[i-1]+a[i]).

Ésta es O(n).

y no puedes conseguir cualquier cosa por debajo de O(n) como usted tiene que visitar cada elemento de la matriz al menos una vez para calcular el resultado.

Answer 2

Bueno, creo que esta es la mejor respuesta.
Ya que necesita O (n) para leer en los datos.
un algoritmo de O (n) es el más rápido en la notación de O grande.

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