Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Определение: |
Последовательность (англ. sequence) — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества. |
Содержание
Виды последовательностей
Определение: |
Последовательность | элементов множества называется неубывающей (англ. nondecreasing), если каждый элемент этой последовательности не превосходит следующего за ним. — неубывающая .
Определение: |
Последовательность | элементов множества называется невозрастающей (англ. nonincreasing), если каждый следующий элемент этой последовательности не превосходит предыдущего. — невозрастающая .
Определение: |
Последовательность | элементов множества называется возрастающей (англ. increasing), если каждый следующий элемент этой последовательности превышает предыдущий. — возрастающая .
Определение: |
Последовательность | элементов множества называется убывающей (англ. decreasing), если каждый элемент этой последовательности превышает следующий за ним. — убывающая .
Определение: |
Последовательность называется монотонной (англ. monotonic), если она является неубывающей, либо невозрастающей. |
Определение: |
Последовательность называется строго монотонной (англ. strictly monotonic), если она является возрастающей, либо убывающей. |
Очевидно, что строго монотонная последовательность является монотонной.
Теорема о связи длины НВП и НУП
Теорема: |
Пусть НВП), — длина наибольшей убывающей подпоследовательности (НУП). Тогда . — перестановка чисел длины — длина наибольшей возрастающей подпоследовательности ( |
Доказательство: |
Рассмотрим два массива длины и , где — длина НВП, которая заканчивается на , — длина НУП, которая начинается на .Докажем, что все пары Заметим что различны. Пусть существуют такие , что = и = . Если , тогда можно добавить к НВП, заканчивающейся на , следовательно . Если , то по аналогии . Противоречие! Следовательно все такие пары различны. , поэтому существуют различных пар . Если тогда среди пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. , ч. т. д. |
Следствие из теоремы
Утверждение: |
Пусть — длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше . |
См. также
- Задача о минимуме/максимуме скалярного произведения
- Теорема Кэли
- Матричное представление перестановок