最長増加部分列・最長共通部分列 [いかたこのたこつぼ]

ある数列や文字列 $A=\{a_1,a_2,...,a_n\}$ がある時、部分列（Subsequence）とは、$A$ からいくつかの要素を抽出した列。飛び飛びでもよいが、順番は元から変わってはいけない。 $A$の部分列 $B=\{a_i,a_j,...,a_k\}$、ただし $1 \le i \lt j \lt ... \lt k \le n$