Bài toán tìm chiều dài của dãy con tăng dần dài nhất

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Tìm chiều dài của dãy con tăng dần dài nhất trong mảng? Để giải bài toán này, CodeGym sẽ cung cấp cho bạn bốn đoạn mã nguồn quan trọng, bao gồm: Pseudo-code, Java, PHP và Python. Thuật toán này khá quan trọng với nhiều ứng dụng thực tế và thường xuất hiện trong các cuộc phỏng vấn công nghệ. Hãy cùng CodeGym khám phá cách tiếp cận hiệu quả để giải quyết bài toán này nhé.

Đề bài:

Cho một mảng các số nguyên, hãy tìm chiều dài dãy con tăng dần dài nhất (Longest Increasing Subsequence – LIS) trong mảng đó. Một dãy con là một dãy được tạo thành từ các phần tử của mảng mà không cần phải liên tiếp nhưng phải tuân thủ trật tự.

Ví dụ:

Cho mảng số nguyên: [10, 9, 2, 5, 3, 7, 101, 18]
Chiều dài của dãy con tăng dần dài nhất là 4.
Giải thích: Các dãy con dài nhất của mảng này là [2, 3, 7, 101], [2, 5, 7, 101], [2, 3, 7, 18] và [2, 5, 7, 18] đều có độ dài là 4.

1. Pseudo-code:

2. Mã nguồn Java:

3. Mã nguồn PHP:

4. Mã nguồn Python:

Theo bạn, Thuật toán để giải bài này có độ phức tạp là bao nhiêu?

Xem thêm các bài viết thú vị về Thuật toán tại đây!