arrays - suma - subsecuencia creciente mas larga java
Algoritmo para encontrar la subsecuencia máxima de una matriz de números positivos. Captura: No se permiten elementos adyacentes (13)
max (oddIndexSum, evenIndexSum) no funciona
Para el ejemplo que dio, sí. Sin embargo, si tiene algo como: A = [1, 51, 3, 2, 41, 23, 20] , puede tener 51 + 2 + 23 = 76 , o puede tener 51 + 41 + 20 = 112 , que es claramente más grande y también evita elementos adyacentes. ¿Es esto lo que estás buscando?
Por ejemplo, dado
A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.
claramente max(oddIndexSum,evenIndexSum) no funciona.
El principal problema que tengo es que no puedo establecer un criterio de selección para un elemento. Un criterio de rechazo es trivial dado un criterio de selección.
El algoritmo de sub-secuencia máxima estándar no parece ser aplicable aquí. He intentado un enfoque de programación dinámica, pero tampoco puedo llegar a eso. El único enfoque que se me ocurrió fue uno que usara un algoritmo genético.
¿Cómo abordarías esto?
Aquí hay una respuesta hecha usando programación dinámica usando el mismo concepto base que usó MarkusQ. Solo estoy calculando la suma, no la secuencia real, que puede producirse mediante una simple modificación a este ejemplo de código. Me sorprende que nadie haya mencionado esto todavía, porque la programación dinámica parece ser un mejor enfoque en lugar de recursión + memorización.
int maxSeqSum(int *arr, int size) {
int i, a, b, c;
b = arr[0];
a = (arr[1] > arr[0]) ? arr[1]: arr[0];
for(i=2;i<size;i++) {
c = (a > (b + arr[i]))? a : (b + arr[i]);
b = a;
a = c;
}
return a;
}
Edit: Esto es realmente una estupidez de sth, pero no me di cuenta hasta después de que lo publiqué.
Puede hacer esto en un espacio constante y en un tiempo lineal, asumiendo que no necesita realizar un seguimiento de qué artículos contribuyen a la suma final.
Pseudocódigo
sum_excluded_last_item= 0
sum_included_last_item= 0
for each item in list
if (item>0)
last_sum_excluded_last_item= sum_excluded_last_item
sum_excluded_last_item= max(sum_included_last_item, sum_excluded_last_item + item)
sum_included_last_item= last_sum_excluded_last_item + item
else
sum_excluded_last_item= max(sum_excluded_last_item, sum_included_last_item)
sum_included_last_item= sum_excluded_last_item
max_sum= max(sum_excluded_last_item, sum_included_last_item)
Obtener la lista real es un ejercicio que queda al lector. O yo si añades más comentarios. Pero debería ser obvio por el algoritmo.
El código de MarkusQ parece omitir completamente un [2]. No soy lo suficientemente inteligente como para averiguar dónde debería figurar en el cálculo de cuentas.
La respuesta de Chris falla en la lista [9,10,9], produciendo 10 en lugar de 9 + 9 = 18.
Joe no está del todo bien. El vendedor que viaja requiere que visites todas las ciudades, mientras que aquí no hay nada parecido.
Una posible solución sería la solución recursiva:
function Max_route(A)
if A''s length = 1
A[0]
else
maximum of
A[0]+Max_route(A[2...])
Max_route[1...]
Esto tiene la misma gran O como una función ingenua de fibonacci, y debería dar lugar a algunas de las mismas optimizaciones (por ejemplo, memoria) si le importa la eficiencia además de simplemente obtener una respuesta correcta.
- MarkusQ
[Editar] ---
Debido a que algunas personas no parecen estar recibiendo esto, quiero explicar a qué me refiero con memoización y por qué es importante.
Puede ajustar la función anterior para que solo calcule el valor de cada matriz una vez (la primera vez que se llamó), y en las siguientes llamadas simplemente devolvería el resultado guardado. Esto tomaría O (n) espacio pero regresaría en tiempo constante. Eso significa que todo el algoritmo volvería en O (n), mejor que el tiempo exponencial de la versión menos abarrotada de arriba. Estaba asumiendo que esto era bien entendido.
[Segunda edición] ------------------------------
Si ampliamos un poco lo anterior y lo separamos, obtenemos:
f [] :- [],0
f [x] :- [x],x
f [a,b] :- if a > b then [a],a else [b],b
f [a,b,t] :-
ft = f t
fbt = f [b|t]
if a + ft.sum > fbt.sum
[a|ft.path],a+ft.sum
else
fbt
El cual podemos desenrollar en un pseudo-básico usando solo matrices de enteros y booleanos de tamaño n, y las operaciones de 1) indexación de matrices y asignación de matrices indexadas, 2) matemática de enteros, incluyendo comparación, 3) if / then / else, y 4) un solo bucle de O (n):
dim max_sum_for_initial[n],next_to_get_max_of_initial[n],use_last_of_initial[n]
max_sum_for_initial[0] = 0
next_to_get_max_of_initial[0] = -1
use_last_of_initial[0] = false
max_sum_for_initial[1] = a[0]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[1] = true
if a[0] > a[1]
max_sum_for_initial[2] = a[0]
next_to_get_max_of_initial[2] = 0
use_last_of_initial[2] = false
else
max_sum_for_initial[2] = a[1]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[2] = true
for i from 3 to n
if a[i]+max_sum_for_initial[i-2] > max_sum_for_initial[i-1]
max_sum_for_initial[i] = a[i]+max_sum_for_initial[i-2]
next_to_get_max_of_initial[i] = i-2
use_last_of_initial[i] = true
else
max_sum_for_initial[i] = max+sum_for_initial[i-1]
next_to_get_max_of_initial[i] = i-1
use_last_of_initial[i] = false
Al final podemos extraer los resultados (en orden inverso):
for i = n; i >= 0; i = next_to_get_max_of_initial[i]
if use_last_of_initial[i] then print a[i]
Tenga en cuenta que lo que acabamos de hacer manualmente es algo que un buen compilador para un lenguaje moderno debería poder lograr con la recursión de la cola, la memorización, etc.
Espero que eso quede suficientemente claro.
- MarkusQ
Esta encendido).
Para evitar la recursión, podemos tomar de reversa a de adelante,
ie) para el Array A [1..n] ->
maxSum(A,n): for all n
if n=0, maxSum = 0 else
if n=1, maxSum=A[1] else
maxSum = max(A[n] + maxSum(A,n-2), maxSum(A,n-1))
Para evitar el cálculo de Max (A, n-2), mientras se expande maxSum (A, n-1), se puede almacenar y calcular. Por eso pido revertir. es decir, maxSum (A, n-1) = max (A [n-1] + maxSum (A, n-3), maxSum (A, n-2)) donde en Max (A, n-2) ya está obtuve, y no hay necesidad de volver a calcular) En otras palabras, calcule maxSum (A, n) para todas las n empezando de 1 a n utilizando la fórmula anterior para evitar volver a calcular.
ie) n = 2, maxSum = max (A [1] + maxSum (A, 0), maxSum (A, 1)) ie) n = 3, maxSum = max (A [2] + maxSum (A, 2) , maxSum (A, 2)) y así sucesivamente .. y llegue al último n. esto será o (n).
Podemos usar una matriz auxiliar B [0..n-1], donde B [i] es la suma máxima de los elementos A [0..i] y C [0..n-1], donde C [i ] es booleano que indica si A [i] está en la subsecuencia de suma máxima:
B[0]=max(A[0],0); C[0]=(A[0]>0)
B[1]=max(B[0],A[1]); C[1]=(A[1]>B[0])
for i in [2..n-1]
if A[i]+B[i-2] > B[i-1]
C[i]=True
B[i]=A[i]+B[i-2]
else
C[i]=False
B[i]=B[i-1]
mssq=[]
i=n-1
while i>=0
if C[i]
push(A[i],mssq)
i=i-2
else
i=i-1
return mssq
Esto claramente funciona en O (n) tiempo y espacio. En realidad, esto es lo mismo que la solución de MarcusQ, solo invertida y optimizada.
Puede crear la subsecuencia máxima paso a paso si mantiene dos estados:
def maxsubseq(seq):
# maximal sequence including the previous item
incl = []
# maximal sequence not including the previous item
excl = []
for i in seq:
# current max excluding i
if sum(incl) > sum(excl):
excl_new = incl
else:
excl_new = excl
# current max including i
incl = excl + [i]
excl = excl_new
if sum(incl) > sum(excl):
return incl
else:
return excl
print maxsubseq([1,4,6,3,5,7,32,2,34,34,5])
Si también desea tener elementos negativos en sus listas, debe agregar algunos ifs.
Lo mismo - en líneas menores
def maxsubseq2(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
for x in iterable:
# current max excluding x
excl_new = incl if sum(incl) > sum(excl) else excl
# current max including x
incl = excl + [x]
excl = excl_new
return incl if sum(incl) > sum(excl) else excl
Mismo - eliminando sum()
def maxsubseq3(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
incl_sum, excl_sum = 0, 0
for x in iterable:
# current max excluding x
if incl_sum > excl_sum:
# swap incl, excl
incl, excl = excl, incl
incl_sum, excl_sum = excl_sum, incl_sum
else:
# copy excl to incl
incl_sum = excl_sum #NOTE: assume `x` is immutable
incl = excl[:] #NOTE: O(N) operation
assert incl is not excl
# current max including x
incl.append(x)
incl_sum += x
return incl if incl_sum > excl_sum else excl
Muy bien, optimicemoslo ...
Versión con tiempo de ejecución total O (n):
def maxsubseq4(iterable):
incl = [] # maximal sequence including the previous item
excl = [] # maximal sequence not including the previous item
prefix = [] # common prefix of both sequences
incl_sum, excl_sum = 0, 0
for x in iterable:
if incl_sum >= excl_sum:
# excl <-> incl
excl, incl = incl, excl
excl_sum, incl_sum = incl_sum, excl_sum
else:
# excl is the best start for both variants
prefix.extend(excl) # O(n) in total over all iterations
excl = []
incl = []
incl_sum = excl_sum
incl.append(x)
incl_sum += x
best = incl if incl_sum > excl_sum else excl
return prefix + best # O(n) once
Si bien usaste un montón de palabras elegantes, ¿no es esto básicamente un simple problema del gráfico ambulante del vendedor ambulante?
¿Excepto en este caso, está buscando la ruta más cara a través del gráfico (denso)? En este caso, los vértices son solo los números, los bordes no están dirigidos y no tienen peso, y todos los vértices están conectados, excepto a los vértices que habían estado adyacentes a ellos en la lista original.
Una respuesta recursiva en el extraño pseudocódigo prologico:
maxSum([]) = 0
maxSum([x]) = x
maxSum(A) = max(A[0] + maxSum(A[2..n]),
A[1] + maxSum(A[3..n]))
Con el manejo adecuado de los índices fuera de rango.
Edición: Esto se reduce a la mejor respuesta de MarcusQ:
maxSum([]) = 0
maxSum(A) = max(A[0] + maxSum(A[2..n]), maxSum(A[1..n]))
Edición: Aquí hay una versión que devuelve la subsecuencia real en lugar de solo su suma. Estira los límites de mi pseudo-Prolog-C Chimera ad hoc, así que me detengo ahora.
maxSub([]) = []
maxSub(A) = sub1 = [A[0]] + maxSub(A[2..n])
sub2 = maxSub(A[1..n])
return sum(sub1) > sum(sub2) ? sub1 : sub2
La respuesta de @MarkusQ como Python oneliner (modificado como @recursive sugirió en los comentarios):
f = lambda L: L and max([L[0]] + f(L[2:]), f(L[1:]), key=sum)
Ejemplo:
>>> f([1,51,3,1,100,199,3])
[51, 1, 199]
Es ineficiente, pero podría usarse para probar soluciones más rápidas.
Igual - en Emacs Lisp
(defun maxsubseq (L)
"Based on MarkusQ''s and sth''s answers."
(if (not L) L
(let ((incl (cons (car L) (maxsubseq (cddr L))))
(excl (maxsubseq (cdr L))))
(if (> (sum incl) (sum excl)) incl excl))))
(defun sum (L) (apply ''+ L))
Versión iterativa (O (N) si la recursión está disponible)
Se basa en la respuesta de @ sth :
(defun maxsubseq-iter-impl (L excl incl) (let ((next (if (> (car excl) (car incl)) excl incl)) (x (car L))) (if (not L) (cdr next) (maxsubseq-iter-impl (cdr L) next (cons (+ x (car excl)) (cons x (cdr excl))))))) (defun maxsubseq-iter (L) (reverse (maxsubseq-iter-impl L ''(0) ''(0))))
Ejemplo:
(require ''cl) (loop for f in ''(maxsubseq maxsubseq-iter) collect (loop for L in ''((1 51 3 1 100 199 3) (9 10 9)) collect (f L)))
Salida:
(((51 1 199) (9 9)) ((51 1 199) (9 9)))
find_max(int t, int n)
{
if(t>=n)
return 0;
int sum =0, max_sum =0;
for(int i=t; i<n; ++i)
{
sum = sum + A[i];
for(int j=i+2; j<n; ++j)
sum = sum + find_max(A[j], n);
if(sum > max_sum)
max_sum = sum;
}
return max_sum;
}
Lo anterior es una solución recursiva, no la he compilado. Es bastante trivial ver la repetición y convertirla en un DP. Publicaremos eso pronto.
while you still have elements
find the largest element, add it to the sum
remove the element before and after the current