5
Cómo encontrar una subsecuencia creciente de números con suma máxima. Encuentro O (N^2) pero quiero saber O (N log N).¿Cómo encontrar una subsecuencia creciente de números con suma máxima?
Gracias!
A
Respuesta
0
1.) Clasificar su subsecuencia
2.) iterar a través de su lista, añadir el siguiente elemento a elemento anterior
3.) Una vez que llegue a dos elementos de la OMS sumas son mayores que maximum_sum, detener . Todo lo anterior se puede combinar para que sea < = maximum_sum.
Esto asume que está pidiendo que agregue dos elementos para hacer maximum_sum. El concepto general se puede generalizar para las sumas 0-N, donde N es la longitud de sus "números". Sin embargo, no aclaró qué era lo que en realidad estaban agregando juntos, así que hice una suposición. Además, no estoy seguro de si esto le dará la subsecuencia de números "MÁS LARGA", pero le dará una subsecuencia de números en N log N.
Esta fue una pregunta de la entrevista que Amazon.com me preguntó mientras Estaba vomitando mis agallas por la intoxicación alimentaria en la primera ronda de entrevistas. Llegué a la segunda ronda de entrevistas, y no parecían querer avanzar más allá de ese punto. Esperamos que lo hace mejor que yo si esto es una pregunta de la entrevista, así que mi respuesta podría no ser la mejor, pero es de esperar que es mejor que decir que tiene un duplicado ...
es de esperar que esto ayude,
-Brian J. Stinar-
+1
No lo entiendo. Esto pide una suma máxima que aumente la subsecuencia. ¿Cómo se asegura la clasificación para obtener una subsecuencia válida? – IVlad
3
Asumo:
- Usted no se preocupan por la longitud subsecuencia en absoluto.
- subsecuencias no tienen que ser contiguos
Esto hace que un mundo de diferencia!
Solución
Deje una configuración óptima S de subsecuencias crecientes (IS) para una serie A ser un conjunto de los IS de tal manera que cada uno es s en A tenemos exactamente uno de:
sadentro en S- Hay IS
s'enStal quesum(s')> =sum(s)ylargest_element(s')< =largest_element(s)
La configuración óptima S pueden solicitarse tanto por el elemento más grande de las subsecuencias y su suma - la orden debe ser el mismo.Esto es lo que quiero decir con la secuencia más pequeña/más grande más adelante.
Nuestro algoritmo debe encontrar el conjunto óptimo de A y devolver su secuencia más grande. S pueden calcularse por:
S := {[]} //Contains the empty subsequence
for each element x in A:
s_less := (largest sequence in S that ends in less than x)
s := Append x to s_less
s_more := (smallest sequence in S that has sum greater than s)
Remove all subsequences in S that are between s_less and s_more
(they are made obsolete by 's')
Add s to S
El mayor subsecuencia en S es el más grande subsecuencia de la matriz.
Cada paso se puede implementar en O (log n) es S es un árbol binario equilibrado. Los n pasos dan a O (n * log n) complejidad total.
Advertencia: Podría muy probable que sea un poco de + - 1 error (s) en mi código de pseudo - la búsqueda de ellos se deja como de también al lector :)
voy a tratar de dar una ejemplo de concreto. Quizás ayuda a aclarar la idea. La subsecuencia más a la derecha es siempre la mejor hasta el momento, pero las otras son porque en el futuro podrían convertirse en la secuencia más pesada.
curr array | Optimal Subsequences
[] []
//best this we can do with 8 is a simgleton sequence:
[8] [] [8]
//The heaviest sequence we can make ending with 12 is [8,12] for a total of 20
//We still keep the [8] because a couble of 9s and 10s might make it better tahn 8+12
[8,12] [] [8] [8,12]
[8,12,11] [] [8] [8,11] [8,12]
[8,12,11,9] [] [8] [8,9] [8,11] [8,12]
//[8,9,10] makes [8,11] and [8,12] obsolete (remove those).
//It not only is heavier but the last number is smaller.
[8,12,11,9,10] [] [8] [8,9] [8,9,10]
+1
¿Podría ejecutar esto en un ejemplo, por favor? No entiendo lo que estás diciendo. – IVlad
+0
'Eliminar todas las subsecuencias en S que están entre s_less y s_more' Se puede hacer esto en O (log n). Según tengo entendido, necesitarás iterar sobre cada elemento para poder eliminarlo. –
1
Escanee la matriz. Mantenga un árbol de distribución exponiendo cada elemento x a la suma máxima de una subsecuencia que termina en x. Este árbol desplegable está ordenado por x (no el índice de x), y cada nodo está decorado con el máximo del subárbol. Inicialmente, el árbol contiene solo un Sentinel Infinity => 0. Para procesar un nuevo valor y, busque en el árbol el valor z más a la izquierda, tal que y < = z. Coloque z en la raíz. El subárbol máximo hijo izquierdo de M z es la suma máxima de una subsecuencia que y puede extenderse. Inserta (y, M + y) en el árbol. Al final, devuelve el árbol max.
0
Me encontré con una pregunta similar sobre las fuerzas de código. El problema se puede hacer usando árboles de segmentos con compresión de coordenadas o utilizando árboles de búsqueda binarios equilibrados. Consulte los enlaces a continuación para una explicación detallada.
maximum sum increasing sequence
Después de leerlo, puede intentar this pregunta sobre codeforces.
Cuestiones relacionadas
- 1. ¿Cómo puedo encontrar la suma máxima de una subsecuencia usando la programación dinámica?
- 2. de kadane encontrar subarreglo con la suma máxima
- 3. Encontrar la subsecuencia con la suma más grande de elementos en una matriz
- 4. Encuentra la suma de intervalo máxima en una lista de números reales
- 5. La suma máxima de una forma rectangular sub-array
- 6. Encontrar la suma de los números de Fibonacci
- 7. La forma más rápida de encontrar el rango de suma máxima en int []
- 8. shell script + números de suma
- 9. Encontrar una subsecuencia en la secuencia más larga
- 10. creciente decreciente secuencia
- 11. Cómo encontrar la media máxima
- 12. Elegir n números con suma fija
- 13. Suma de todos los números
- 14. O (NlogN) encontrar 3 números que tienen una suma de cualquier T arbitraria en una matriz
- 15. Explicar el algoritmo para resolver el problema de la 'subsecuencia creciente más larga'
- 16. Algoritmo para encontrar la diferencia máxima en una matriz de números
- 17. usando LINQ para encontrar la suma acumulativa de una matriz de números en C#
- 18. ¿Cómo indexar y encontrar números con Lucene.NET?
- 19. eliminar números de una lista sin cambiar la suma total
- 20. Encontrar el valor mediano de un conjunto creciente
- 21. ordenar números por algoritmo de suma
- 22. suma de los números que hacen una secuencia de
- 23. Cálculo de la suma de números enteros en una matriz
- 24. suma de dos números en JavaScript incorrectamente
- 25. suma de dos números sin usar +
- 26. Algoritmo para encontrar la suma máxima de elementos en una matriz tal que no más de k elementos son adyacentes
- 27. Buscar la suma máxima de elementos en el conjunto
- 28. Botón de Excel creciente
- 29. ¿Cómo se encuentra la suma de todos los números en una matriz en Java?
- 30. Divida una lista de números en una lista más pequeña con "suma" aproximadamente igual
Pregunta duplicada: http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming – payne
@payne que es O (N^2) pero yo quiere encontrar O (N log N). –
Esa página de preguntas duplicadas tiene un enlace a los algoritmos O (n log n), aquí: http://en.wikipedia.org/wiki/Longest_increasing_subsequence – payne