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

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

Определения

Последовательность [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]a[/math] - перестановка чисел длины [math]n, l[/math] - длина наибольшей возрастающей подпоследовательности (НВП), [math]k[/math] - длина наибольшей убывающей подпоследовательности (НУП). Тогда [math]l k \geqslant n[/math].

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

[math]\triangleright[/math]

Рассмотрим два массива длины [math]n : S [/math] и [math] T [/math], где [math] S_i [/math] - длина НВП, которая заканчивается на [math]a_i[/math], [math] T_i [/math] - длина НУП, которая начинается на [math]a_i[/math]. Докажем, что все пары [math](S_i, T_i)[/math] различны. Пусть существуют такие [math]i \lt j[/math] , что [math] S_i [/math] = [math] S_j [/math] и [math] T_i [/math] = [math] T_j[/math]. Если [math]a_i \lt a_j[/math], тогда [math] a_j [/math] можно добавить к НВП, заканчивающейся на [math] a_i [/math], следовательно [math]S_j \geqslant S_i + 1[/math]. Если [math]a_i \gt a_j[/math], то по аналогии [math]T_i \geqslant T_j + 1[/math]. Противоречие! Следовательно все такие пары различны. Заметим что [math]1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k[/math], поэтому существуют [math]l k[/math] различных пар [math] (S_i, T_i) [/math]. Если [math]l k \lt n[/math] тогда среди [math] n [/math] пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. [math]l k \geqslant n[/math], ч. т. д.

[math]\triangleleft[/math]

Следствие из теоремы

Утверждение:

Пусть [math]n[/math] - длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше [math]\sqrt{n}[/math]

Источники

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

• Longest increasing subsequence - Wikipedia, the free encyclopedia