La subsecuencia alterna más larga

---

En matemática combinatoria , probabilidad e informática , en el problema de subsecuencia alterna más largo , se desea encontrar una subsecuencia de una secuencia dada en la que los elementos están en orden alternado y en la que la secuencia es lo más larga posible.

Formalmente, si es una secuencia de números reales distintos, entonces la subsecuencia alterna ^[1] (o en zigzag o hacia abajo ) si${\ Displaystyle \ mathbf {x} = \ {x_ {1}, x_ {2}, \ ldots, x_ {n} \}}$${\ Displaystyle \ {x_ {i_ {1}}, x_ {i_ {2}}, \ ldots, x_ {i_ {k}} \}}$

De manera similar, ¿se alterna en reversa (o de arriba a abajo ) si ${\ Displaystyle \ mathbf {x}}$

Dejar que denotan la longitud (número de términos) de la subsecuencia alterna más largo de . Por ejemplo, si consideramos algunas de las permutaciones de los enteros 1, 2, 3, 4, 5, tenemos que${\ Displaystyle {\ rm {as}} _ {n} (\ mathbf {x})}$${\ Displaystyle \ mathbf {x}}$

El problema de subsecuencia alterna más largo se puede resolver en el tiempo , donde es la longitud de la secuencia original. ^{[ cita requerida ]}${\ Displaystyle O (n)}$${\ Displaystyle n}$

Si es una permutación aleatoria de los números enteros y , entonces es posible mostrar ^{[2] [3] [4]} que${\ Displaystyle \ mathbf {x}}$${\ Displaystyle 1,2, \ ldots, n}$${\ Displaystyle A_ {n} \ equiv {\ rm {as}} _ {n} (\ mathbf {x})}$

---