13
правок
Изменения
→Теорема о связи длины НВП и НУП
== Теорема о связи длины НВП и НУП ==
|proof=
Пусть есть стока <tex> a </tex>. Рассмотрим наибольшую возрастающую подпоследовательность
<tex> a[i_1] < a[i_2] < \dots < a[i_k] </tex> и наибольшую убывающую подпоследовательность <tex> x[j_1] > x[j_2] < \dots > x[j_l] </tex> строки <tex> a </tex>.
}}
== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Wikipedia Последовательность]
