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

Определение:

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

Виды последовательностей

Определение:

Последовательность [math]\{x_n\}[/math] элементов множества [math]X[/math] называется неубывающей (англ. nondecreasing), если каждый элемент этой последовательности не превосходит следующего за ним. [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] называется невозрастающей (англ. nonincreasing), если каждый следующий элемент этой последовательности не превосходит предыдущего. [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] называется возрастающей (англ. increasing), если каждый следующий элемент этой последовательности превышает предыдущий. [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] называется убывающей (англ. decreasing), если каждый элемент этой последовательности превышает следующий за ним. [math]\{x_n\}[/math] — убывающая [math]\Leftrightarrow\forall n \in \mathbb N: x_n \gt x_{n+1}[/math].

Определение:

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

Определение:

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

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

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

Теорема:

Пусть [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