Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Определение: |
Последовательность (англ. sequence) — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. |
Содержание
Виды последовательностей
Определение: |
Последовательность | элементов множества называется неубывающей (англ. nondecreasing), если каждый элемент этой последовательности не превосходит следующего за ним. — неубывающая .
Определение: |
Последовательность | элементов множества называется невозрастающей (англ. nonincreasing), если каждый следующий элемент этой последовательности не превосходит предыдущего. — невозрастающая .
Определение: |
Последовательность | элементов множества называется возрастающей (англ. increasing), если каждый следующий элемент этой последовательности превышает предыдущий. — возрастающая .
Определение: |
Последовательность | элементов множества называется убывающей (англ. decreasing), если каждый элемент этой последовательности превышает следующий за ним. — убывающая .
Определение: |
Последовательность называется монотонной (англ. monotonic), если она является неубывающей, либо невозрастающей. |
Определение: |
Последовательность называется строго монотонной (англ. strictly monotonic), если она является возрастающей, либо убывающей. |
Очевидно, что строго монотонная последовательность является монотонной.
Теорема о связи длины НВП и НУП
Теорема: |
Пусть НВП), — длина наибольшей убывающей подпоследовательности (НУП). Тогда . — перестановка чисел длины — длина наибольшей возрастающей подпоследовательности ( |
Доказательство: |
Рассмотрим два массива длины и , где — длина НВП, которая заканчивается на , — длина НУП, которая начинается на .Докажем, что все пары Заметим что различны. Пусть существуют такие , что = и = . Если , тогда можно добавить к НВП, заканчивающейся на , следовательно . Если , то по аналогии . Противоречие! Следовательно все такие пары различны. , поэтому существуют различных пар . Если тогда среди пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. , ч. т. д. |
Следствие из теоремы
Утверждение: |
Пусть — длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше . |
См. также
- Задача о минимуме/максимуме скалярного произведения
- Теорема Кэли
- Матричное представление перестановок