Algorithms/Misc - tmura's note - atwiki（アットウィキ）

Algorithms > Misc

$n$ 個の正整数の列 $x_1,x_2,...,x_n$ が与えられたとする。
簡単のために $n$ は $\sqrt{n}$ が整数になるような数、 $x_1,x_2,...,x_n$ は全て異なるとする。
すると、少なくとも長さ $\sqrt{n}$ の増加部分列か減少部分列が存在する。

最終更新：2012年02月07日 11:56