Yêu cầu: Tìm độ dài lớn nhất của một dãy con mà các phần tử đứng sau luôn lớn hơn phần tử đứng trước.
Đặc điểm: Với , chúng ta có thể sử dụng thuật toán có độ phức tạp .
2. Ý tưởng Quy hoạch động
Gọi dp[i] là độ dài của dãy con tăng dài nhất kết thúc tại phần tử .
Để tính dp[i], ta nhìn lại các phần tử đứng trước nó ():
Nếu , ta có thể kéo dài dãy con kết thúc tại bằng cách thêm vào sau. Khi đó độ dài mới sẽ là dp[j] + 1.
Ta chọn giá trị lớn nhất có thể đạt được.
3. Các bước thuật toán
Khởi tạo: Tạo một mảng dp có phần tử, tất cả giá trị ban đầu bằng (vì mỗi phần tử đứng một mình luôn là một dãy con tăng độ dài 1).
Duyệt và cập nhật:
Chạy vòng lặp i từ đến .
Với mỗi i, chạy vòng lặp j từ đến .
Nếu :
Cập nhật: dp[i] = max(dp[i], dp[j] + 1).
Kết quả: Đáp án của bài toán là giá trị lớn nhất trong mảng dp.
4. Lưu ý khi triển khai
C++: Có thể dùng hàm *max_element(dp, dp + n) để tìm kết quả cuối cùng.
Python: Dùng max(dp) để lấy độ dài lớn nhất.
Điều kiện "tăng nghiêm ngặt": Phải là . Nếu đề bài cho phép các phần tử bằng nhau (dãy không giảm), bạn sẽ đổi thành .
Giới hạn: Với lớn hơn (ví dụ ), thuật toán này sẽ bị quá thời gian (TLE), khi đó cần dùng kỹ thuật kết hợp Tìm kiếm nhị phân để đạt độ phức tạp . Tuy nhiên với , cách là đơn giản và hiệu quả nhất.
