Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

Последовательность — это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.

Определения

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется неубывающей, если каждый элемент этой последовательности не превосходит следующего за ним.

[math]\{x_n\}[/math] — неубывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}[/math]

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется невозрастающей, если каждый следующий элемент этой последовательности не превосходит предыдущего.

[math]\{x_n\}[/math] — невозрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}[/math]

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется возрастающей, если каждый следующий элемент этой последовательности превышает предыдущий.

[math]\{x_n\}[/math] — возрастающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \lt x_{n+1}[/math]

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется убывающей, если каждый элемент этой последовательности превышает следующий за ним.

[math]\{x_n\}[/math] — убывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \gt x_{n+1}[/math]

Последовательность называется монотонной, если она является неубывающей, либо невозрастающей.

Последовательность называется строго монотонной, если она является возрастающей, либо убывающей.

Очевидно, что строго монотонная последовательность является монотонной.

Теорема о связи длины НВП и НУП

Теорема:

Произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей больше либо равно длине последовательности.

Доказательство:

[math]\triangleright[/math]

Пусть есть стока [math] a [/math] длины [math] n [/math]. Рассмотрим наибольшую возрастающую подпоследовательность [math] a[i_1] \lt a[i_2] \lt \dots \lt a[i_k] [/math] и наибольшую убывающую подпоследовательность [math] x[j_1] \gt x[j_2] \gt \dots \gt x[j_l] [/math] строки [math] a [/math].

[math]\triangleleft[/math]

Источники

• Wikipedia Последовательность

• Longest increasing subsequence - Wikipedia, the free encyclopedia