Cómo encontrar la longitud de LIS usando dos números. Por ejemplo, [(1,2) (7,8) (3,4) (5,6)] En la secuencia de matriz anterior, la longitud de LIS sería 3. es decir, [(1,2) (3,4) (5,6)] ¿Alguna idea?Subsección de aumento más larga (LIS) con dos números
usted podría utilizar cualquier algorithm para el estándar LIS problem, con dos modificaciones:
A < B) tiene que comparar el segundo número de la A a la primera serie de B.Siempre que el primer y segundo número en las tuplas sean siempre ascendentes (lo que parece ser el caso de su ejemplo), esto en principio no debería ser diferente de regular LIS algorithm además de algunas modificaciones menores: simplemente aumente el LIS máximo hasta el tupla actual para la cual el último número es menor que el primer número de la tupla actual. Utilice la programación dinámica para almacenar en caché un LIS máximo y una tupla predecesora para cada punto de secuencia.
Usted tendrá que encontrar los LIS primero y luego calcular su cardinalidad
creo que se puede utilizar el algoritmo LIS estándar con la pequeña excepción de que -
cuando se compara con el índice i el índice i + 1 - comparar el valor superior de I con el menor valor de i + 1.
EDITAR: Esto es, por supuesto, suponiendo que todos los rangos tienen el número más bajo primero y el número superior a continuación.
Represente el problema como un gráfico. Cada tupla puede ser un nodo. Existe un borde dirigido de un nodo a otro si la primera tupla es estrictamente menor que la segunda (aquí "menos" significa que ambos valores de la tupla son menores).
La subsecuencia creciente más larga es ahora la ruta más larga en este gráfico. Observe que no puede haber ciclos en este gráfico (es decir, es un DAG). La ruta más larga en un DAG se puede encontrar mediante programación dinámica (consulte wikipedia).
No estoy seguro de lo que está preguntando pero supongo que lo que quiere decir es que un par (a, b) es menor que otro par (c, d) si y solo si es < c y b < d .
Esto se puede resolver fácilmente en O (N^2) tiempo adaptando la técnica de programación dinámica estándar, que se describe in another SO thread.
El O (N log N) solution to the standard LIS problem clásico se puede extender para dar una solución subcuadrática al problema de LIS con pares, con cierta dificultad. No podemos simplemente recordar un valor mínimo para cada longitud posible; tenemos que mantener estructuras "similares a una escalera" que contengan todos los pares mínimos para cada longitud, es decir, hasta N copias de la estructura de datos descrita here, implementada utilizando un conjunto dinámico ordenado de pares codificados en el primer miembro. Luego podemos consultar una copia de esta estructura en el tiempo O (log N) (para verificar si contiene algún par menor que el par actual), dando O (log^2 N) tiempo para el paso de búsqueda binaria, y O (N log^2 N) tiempo en total. Esta es la solución más rápida que conozco para el problema.
Proceda como lo hacemos en caso de encontrar LIS de matriz simple. Justo al lado de hacer solo una comparación, compare ambos elementos. Le dará LIS con O (n^2) complejidad de tiempo.
¿Cómo se ve menos que? Es (1, 5) <(2, 6)? Si es así, la respuesta marcada a continuación no funcionará. –