Sau đây là chương trình Java cho dãy con tăng dài nhất -
Ví dụ
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));
}
} Đầu ra
The length of the longest increasing subsequence is 5
Một lớp có tên Demo chứa một hàm tĩnh có tên 'incre_subseq' lấy mảng và độ dài của mảng làm tham số. Bên trong hàm này, một mảng mới được tạo trống. Một biến 'max' được gán giá trị 0. Vòng lặp 'for' lặp lại theo chiều dài của mảng và mọi phần tử được khởi tạo thành 1.
Một lần nữa, vòng lặp 'for' được lặp lại và một vòng lặp 'for' khác được bắt đầu để kiểm tra xem phần tử đầu tiên trong mảng có bằng phần tử thứ hai không và nếu mảng (seq_arr, đã khởi tạo tất cả 1s) có phần tử đầu tiên nhỏ hơn phần tử thứ hai + 1. Phần tử tối đa trong seq_arr được tìm thấy và trả về. Đây là kỹ thuật lập trình động, trong đó một giá trị được tính toán và lưu trữ trong một mảng, loại bỏ nhu cầu tính toán nó nhiều lần như trong đệ quy. Bất cứ khi nào một phần tử đã tính toán trước đó được yêu cầu, nó sẽ được tìm nạp từ mảng.