Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Последовательность — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
Определения
Последовательность элементов множества называется неубывающей, если каждый элемент этой последовательности не превосходит следующего за ним.
— неубывающая
Последовательность элементов множества называется невозрастающей, если каждый следующий элемент этой последовательности не превосходит предыдущего.
— невозрастающая
Последовательность элементов множества называется возрастающей, если каждый следующий элемент этой последовательности превышает предыдущий.
— возрастающая
Последовательность элементов множества называется убывающей, если каждый элемент этой последовательности превышает следующий за ним.
— убывающая
Последовательность называется монотонной, если она является неубывающей, либо невозрастающей.
Последовательность называется строго монотонной, если она является возрастающей, либо убывающей.
Очевидно, что строго монотонная последовательность является монотонной.
Теорема о связи длины НВП и НУП
| Теорема: |
Произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей больше либо равно длине последовательности. |
| Доказательство: |
|
Пусть есть стока длины . Рассмотрим наибольшую возрастающую подпоследовательность и наибольшую убывающую подпоследовательность строки . |
