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

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

Последовательность (англ. 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