最長増加部分列（LIS）問題を解くJavaプログラム：動的計画法による実装

最長増加部分列（Longest Increasing Subsequence、略称LIS）とは、配列の中から元の順序を保ったまま要素を選び、値が厳密に増加していくような部分列のうち、最も長いものを指します。以下は、動的計画法を用いてLISの長さを求めるJavaプログラムです。

サンプルコード

public class Demo{
   static int incre_subseq(int my_arr[], int arr_len){
      int seq_arr[] = new int[arr_len];
      int i, j, max = 0;
      for (i = 0; i < arr_len; i++)
         seq_arr[i] = 1;
      for (i = 1; i < arr_len; i++)
      for (j = 0; j < i; j++)
      if (my_arr[i] > my_arr[j] && seq_arr[i] < seq_arr[j] + 1)
      seq_arr[i] = seq_arr[j] + 1;
      for (i = 0; i < arr_len; i++)
      if (max < seq_arr[i])
      max = seq_arr[i];
      return max;
   }
   public static void main(String args[]){
      int my_arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
      int arr_len = my_arr.length;
      System.out.println("The length of the longest increasing subsequence is " +  incre_subseq(my_arr, arr_len));
   }
}

実行結果

The length of the longest increasing subsequence is 5

プログラムの解説

Demoという名前のクラスには、配列とその長さを引数として受け取る静的メソッド「incre_subseq」が定義されています。このメソッド内では、まず入力配列と同じ長さの新しい配列「seq_arr」を作成し、「max」変数を0で初期化します。続くforループで、seq_arrのすべての要素を1に初期化します。これは「各位置を終点とする増加部分列の長さは最低でも1」という意味を持っています。

次に、二重のforループによって動的計画法の核心となる処理を行います。外側のループで現在の位置iを、内側のループでそれより前の位置jを順に走査し、「my_arr[i] > my_arr[j]」（現在の要素が前の要素より大きい）かつ「seq_arr[i] < seq_arr[j] + 1」が成り立つ場合に、seq_arr[i]をseq_arr[j] + 1で更新します。これにより、各位置iで終わる最長増加部分列の長さが段階的に求まります。

最後に、seq_arrの中から最大値を探索して返します。この値が、配列全体における最長増加部分列の長さとなります。上記の例では {10, 22, 33, 50, 60} のような長さ5の増加部分列が存在するため、結果として5が出力されます。

動的計画法のポイント

このプログラムで採用されているのは動的計画法（Dynamic Programming）という手法です。一度計算した値を配列に格納しておくことで、再帰的なアプローチのように同じ計算を何度も繰り返す無駄を省けます。過去に計算済みの要素が必要になったときは、配列から即座に取り出して利用できます。このアルゴリズムの計算量はO(n²)であり、すべての部分列を総当たりで調べる方法（指数時間）と比べて大幅に効率的です。