Dưới đâ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("Độ dài dãy con tăng dài nhất là: " + incre_subseq(my_arr, arr_len));
}
}
Kết quả
Độ dài dãy con tăng dài nhất là 5
Lớp Demo chứa hàm tĩnh incre_subseq nhận mảng và độ dài. Bên trong, mảng mới được tạo rỗng. Biến max gán 0. Vòng for duyệt độ dài mảng và khởi tạo mọi phần tử bằng 1.
Lại vòng for lặp, và vòng for khác kiểm tra nếu phần tử đầu lớn hơn phần tử thứ hai và mảng seq_arr (khởi tạo toàn 1) có phần tử đầu nhỏ hơn phần tử thứ hai + 1. Giá trị lớn nhất trong seq_arr được tìm và trả về. Đây là kỹ thuật quy hoạch động (dynamic programming) - giá trị tính trước lưu trong mảng, tránh tính lại như đệ quy.