Đây là bài toán cơ bản của phương pháp quy hoạch động thôi mà: Tìm dãy con không giảm dài nhất của N phần tử cho trước.
Các làm rất đơn giản
Code:
Gọi F[i] là độ dài dãy không giảm dài nhất từ phần từ a[1] đến a[i]
Khi đo, F[i] được tính bằng công thức:
F[i] = F[j] + 1 với j = 1..i-1; a[i] >= a[j] và F[j] là lớn nhất.
Có thể tìm được F[j] bằng 1 vòng lặp, nếu không tìm thấy thì F[i] = 1
Độ phức tạp thông thường là O(N^2), nếu cải tiến bằng cách chia nhị phân tìm kiếm j hoặc dùng cấu trúc Interval Tree thì độ phức tạp còn lại là O(N*log(2, N)). Sau khi tìm được F[i] với mọi i = 1..N rồi thì cứ dựa vào công thức trên mà truy vết thôi.
Bài toán này là bài toán đầu tiên mà sách thuật toán nào nói về quy hoạch động cũng nói đến.
Với những câu sau thì chỉ cần cải tiến rất nhỏ từ thuật toán trên là được.