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