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