Dãy con tăng dài nhất (LIS)

Chọn các số từ một danh sách, từ trái sang phải, mỗi số lớn hơn số trước. Một chuỗi như vậy có thể dài đến đâu? Câu hỏi đủ đơn giản để in trong sách đố, còn câu trả lời của nó kết nối một trò chơi bài, một bảng quy hoạch động kinh điển và một trong những kết quả đẹp nhất về hoán vị ngẫu nhiên.

Một hàng cột có chiều cao khác nhau, trong đó một chuỗi cột tăng dần từ trái sang phải được tô màu cam
Một hàng cột có chiều cao khác nhau, trong đó một chuỗi cột tăng dần từ trái sang phải được tô màu cam

Bài toán

Cho một danh sách số, một dãy con giữ lại một số phần tử theo thứ tự ban đầu. Dãy con là tăng nếu mỗi giá trị lớn hơn giá trị trước. Dãy con tăng dài nhất, hay LIS, là cách chọn như vậy dài nhất. Một danh sách n giá trị có 2ⁿ dãy con, nên kiểm tra tất cả chỉ khả thi với danh sách rất ngắn.

Bảng

Gọi len[i] là độ dài dãy con tăng dài nhất kết thúc đúng tại vị trí i. Nó bằng 1 với riêng giá trị đó, hoặc 1 + len[j] với một vị trí j trước đó có giá trị nhỏ hơn, lấy giá trị lớn nhất. Mỗi vị trí nhìn lại mọi vị trí trước, nên bảng cần n·(n − 1)/2 phép so sánh. Đáp án là len[i] lớn nhất, và ghi lại j nào cho ra mỗi len[i] giúp đọc ngược được dãy con.

Một ví dụ

Lấy 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Theo từng vị trí, độ dài lần lượt là 1, 2, 1, 1, 3, 2, 3, 4, 3 và 5: số 20 nối dài 3, 10; số 4 nối dài 3; số 6 nối dài 4, số 7 nối dài 6, và số 9 nối dài 7. Đọc ngược từ số 9 được 3, 4, 6, 7, 9, một dãy con tăng độ dài 5.

Cách nhanh hơn: sắp xếp patience

Chia các giá trị như chia bài thành các chồng: mỗi giá trị đặt lên chồng bên trái nhất có lá trên cùng không nhỏ hơn nó, hoặc mở một chồng mới bên phải. Số chồng chính là độ dài LIS. Vì các lá trên cùng luôn được sắp xếp, có thể tìm chồng phù hợp bằng tìm kiếm nhị phân, nên cả phương pháp chỉ mất O(n log n) bước. Tên gọi đến từ trò chơi bài solitaire (patience) mà nó giống.

Một chút toán học

Năm 1935, Paul Erdős và George Szekeres chứng minh rằng mọi danh sách gồm n² + 1 số khác nhau đều có một dãy con tăng hoặc giảm độ dài n + 1. Năm 1961, Stanislaw Ulam đặt câu hỏi LIS của một hoán vị ngẫu nhiên n số dài bao nhiêu. Câu trả lời, gần 2√n khi n lớn, được xác lập năm 1977 bởi Anatoly Vershik và Sergei Kerov, cũng như bởi Ben Logan và Larry Shepp; năm 1999, Jinho Baik, Percy Deift và Kurt Johansson tìm ra hình dạng chính xác của các dao động của nó: phân phối Tracy–Widom từ lý thuyết ma trận ngẫu nhiên.

Paul Erdős tại một buổi seminar sinh viên ở Budapest năm 1992. Năm 1935 ông và George Szekeres chứng minh rằng mọi danh sách gồm n² + 1 số khác nhau đều có một dãy con tăng hoặc giảm độ dài n + 1.
Paul Erdős tại một buổi seminar sinh viên ở Budapest năm 1992. Năm 1935 ông và George Szekeres chứng minh rằng mọi danh sách gồm n² + 1 số khác nhau đều có một dãy con tăng hoặc giảm độ dài n + 1.
Chân dung Stanisław Ulam
Chân dung Stanisław Ulam

Khám phá

Mở ứng dụng và nhấn Bước. Cột màu cam là vị trí đang được tính, còn cột màu xanh là vị trí trước đó đang được so sánh. Hàng Độ dài tăng lên khi tìm được chuỗi dài hơn, hàng Đứng sau ghi nhớ chúng đến từ đâu, và cuối cùng đáp án được đọc ngược bằng màu cam và hiện dưới bảng.

Câu hỏi thường gặp

Độ phức tạp thời gian của LIS là bao nhiêu?

O(n²) với bảng, vì mỗi vị trí xem xét mọi vị trí trước, và O(n log n) với sắp xếp patience và tìm kiếm nhị phân. Cả hai đều cần bộ nhớ O(n).

Làm sao tìm dãy con không giảm dài nhất?

Cho phép một giá trị đứng sau giá trị bằng nó: so sánh bằng ≤ thay vì <. Trong ứng dụng, đánh dấu Cho phép giá trị bằng nhau. Với sắp xếp patience, đặt mỗi giá trị lên chồng bên trái nhất có lá trên cùng lớn hơn hẳn nó.

Dãy con giảm dài nhất là gì?

Cùng bài toán nhưng đảo chiều phép so sánh, hoặc LIS của danh sách sau khi đổi dấu mọi giá trị. Theo định lý Erdős–Szekeres, một danh sách đủ dài luôn có một dãy con tăng dài hoặc một dãy con giảm dài.

LIS của một danh sách ngẫu nhiên dài bao nhiêu?

Với một hoán vị ngẫu nhiên của n số khác nhau, gần 2√n khi n lớn. Phần hiệu chỉnh tăng như căn bậc sáu của n, nên với một nghìn số, trung bình khoảng 58, thấp hơn một chút so với 2√1000 ≈ 63.

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.

Thử dãy con tăng dài nhất