- Đang điền
- Được đọc
- Đáp án
Dãy con tăng dài nhất (LIS)
Trong một danh sách số, có thể chọn được bao nhiêu số, giữ nguyên thứ tự, sao cho số sau luôn lớn hơn số trước? Dãy con tăng dài nhất trả lời câu hỏi đó. Nhập một danh sách và xem quy hoạch động tìm ra, cho từng vị trí, chuỗi dài nhất kết thúc tại đó. Nhấn Phát để xem bảng được điền dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhập một danh sách số. Với mỗi vị trí, bảng lưu độ dài của chuỗi giá trị tăng dài nhất kết thúc tại đó, và vị trí trước đó mà chuỗi ấy nối tiếp. Đánh dấu Cho phép giá trị bằng nhau để tìm chuỗi không bao giờ giảm. Cuối cùng, chuỗi được đọc ngược từ giá trị cuối của nó. Ví dụ mới tạo một danh sách khác. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhập một danh sách số, cách nhau bằng dấu phẩy hoặc dấu cách. Đánh dấu Cho phép giá trị bằng nhau để tìm chuỗi không bao giờ giảm.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Xem mỗi vị trí được so sánh với mọi vị trí trước nó, rồi xem chuỗi dài nhất được đọc ngược bằng màu cam.
Bảng hoạt động thế nào
Bảng có ba hàng: các giá trị, độ dài của dãy con tăng dài nhất kết thúc tại mỗi vị trí, và vị trí mà nó nối tiếp. Một giá trị đứng riêng là một chuỗi độ dài 1. Sau đó mọi vị trí trước được kiểm tra: nếu giá trị ở đó nhỏ hơn, chuỗi kết thúc tại đó có thể được nối dài bằng giá trị này, cho độ dài hơn nó một. Cách nối dài nhất sẽ thắng, và vị trí của nó được ghi vào hàng thứ ba.
Đọc ngược chuỗi
Dãy con tăng dài nhất kết thúc tại vị trí có độ dài lớn nhất. Từ đó, hàng thứ ba cho biết vị trí nào đứng trước nó, và hàng thứ ba của vị trí ấy cho biết vị trí nào đứng trước nữa, cho đến khi gặp một vị trí không có gì đứng trước. Đọc theo thứ tự, các giá trị đó chính là đáp án. Khi đánh dấu Cho phép giá trị bằng nhau, một giá trị cũng có thể đứng sau một giá trị bằng nó, cho ra chuỗi dài nhất không bao giờ giảm.
Câu hỏi thường gặp
Dãy con và mảng con khác nhau thế nào?
Mảng con là một khối các giá trị liền kề. Dãy con giữ thứ tự nhưng có thể bỏ qua giá trị, nên trong 3, 10, 2, 1, 20, các giá trị 3, 10 và 20 tạo thành một dãy con tăng dù 2 và 1 nằm giữa chúng.
Thuật toán LIS nhanh đến đâu?
Phương pháp bảng so sánh mọi cặp vị trí: n·(n − 1)/2 phép so sánh cho n giá trị. Sắp xếp patience làm được trong O(n log n): với mỗi độ dài, nó giữ giá trị nhỏ nhất kết thúc một chuỗi có độ dài đó, và đặt từng giá trị mới bằng tìm kiếm nhị phân.
Dãy con tăng dài nhất có duy nhất không?
Không phải lúc nào cũng vậy. Trong 1, 3, 2, 4, cả 1, 3, 4 và 1, 2, 4 đều có độ dài 3. Bảng cho biết độ dài, còn bước đọc ngược tìm ra một trong số đó.
Dãy con tăng dài nhất được dùng ở đâu?
Trong so sánh tệp và bộ gen, khi một số phương pháp trước hết tìm các dòng khớp nhau rồi lấy một dãy con tăng của các vị trí của chúng; trong lập lịch và các câu đố xếp chồng hộp; và trong toán học, nơi độ dài LIS của một hoán vị ngẫu nhiên là một đối tượng nghiên cứu nổi tiếng.
Có dữ liệu nào được gửi đi đâu không?
Không. Mọi thứ được tính trong trình duyệt của bạn, và thiết lập gần nhất của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa