가장 긴 증가 부분 시퀀스를 위한 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' 루프가 반복되고 배열의 첫 번째 요소가 두 번째 요소와 동일한지, 그리고 배열(seq_arr, 모두 1이 초기화됨)이 첫 번째 요소보다 작은지 확인하는 또 다른 'for' 루프가 시작됩니다. 두 번째 요소 + 1. seq_arr에서 요소의 최대값을 찾아 반환합니다. 이것은 하나의 값을 계산하여 배열에 저장하는 동적 프로그래밍 기법으로, 재귀에서처럼 반복해서 계산할 필요가 없습니다. 이전에 계산된 요소가 필요할 때마다 배열에서 가져옵니다.