最長増加部分列 - きままにものづくり

最長増加部分列 - きままにものづくり

目次 最長増加部分列とは アルゴリズム 最長増加部分列とは？ 与えられるデータの配列をaとする。 かつ ...概要を表示 目次 最長増加部分列とは アルゴリズム 最長増加部分列とは？ 与えられるデータの配列をaとする。 かつ を満たす最長の部分列のこと。 アルゴリズム 最長増加部分列の個数を求めるアルゴリズムを説明する。 漸化式の作り方は2種類ある。 dp[i] := を最後の要素とする増加部分列の最大の長さ。 dp[i] := i+1の部分列の最後の要素となる最小の値。 1の場合のソースは以下となる。 int getLIS() { int dp[MAX_P]; int res = 0; for (int i=0; i<P; ++i) { dp[i] = 1; for (int j=0; j<i; ++j) { if (a[j] < a[i]) { dp[i] = max(dp[i],dp[j]+1); } } res = max(res,dp[i]); } return res; } このアルゴリズムの計算