最長増加部分列問題のためのJavaプログラム

以下は、最長増加部分列問題の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'という名前の静的関数が含まれています。この関数内に、空の新しい配列が作成されます。 'max'変数には値0が割り当てられます。'for'ループは配列の長さにわたって繰り返され、すべての要素が1に初期化されます。

この場合も、「for」ループが繰り返され、別の「for」ループが開始され、配列の最初の要素が2番目の要素と等しいかどうか、および配列（seq_arr、すべて1が初期化されている）の最初の要素が2番目の要素+1。seq_arr内の要素の最大値が検出され、返されます。これは動的計画法であり、1つの値が計算されて配列に格納されるため、再帰のように何度も計算する必要がなくなります。以前に計算された要素が必要な場合は常に、配列からフェッチされます。