โปรแกรม 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' วนรอบเริ่มต้นที่ตรวจสอบว่าองค์ประกอบแรกในอาร์เรย์เท่ากับองค์ประกอบที่สองและถ้าอาร์เรย์ (seq_arr ที่มีการเริ่มต้นทั้งหมด 1 วินาที) มีองค์ประกอบแรกน้อยกว่า องค์ประกอบที่สอง + 1 จำนวนสูงสุดขององค์ประกอบใน seq_arr ถูกพบและส่งคืน นี่เป็นเทคนิคการเขียนโปรแกรมแบบไดนามิกที่มีการคำนวณและจัดเก็บค่าหนึ่งค่าในอาร์เรย์ ทำให้ไม่จำเป็นต้องคำนวณซ้ำแล้วซ้ำอีกเหมือนกับการเรียกซ้ำ เมื่อใดก็ตามที่จำเป็นต้องใช้องค์ประกอบที่คำนวณไว้ก่อนหน้านี้ องค์ประกอบนั้นจะถูกดึงมาจากอาร์เรย์