Hậu quả tăng dài nhất (LIS) với hai số

Question

Cách tìm độ dài của LIS bằng hai số. Ví dụ: [(1,2) (7,8) (3,4) (5,6)] Trong dãy thứ tự trên, chiều dài của LIS sẽ là 3. ví dụ: [(1,2) (3,4) (5,6)] Bất kỳ ý tưởng nào?

Answer 1

Bạn có thể sử dụng bất kỳ algorithm cho các tiêu chuẩn LIS problem, với hai thay đổi:

1. Bỏ bất kỳ cặp có số thứ hai là không nghiêm chỉnh lớn hơn số đầu tiên.
2. Các toán tử so sánh với cặp A và B (tức là A < B) cần phải so sánh số thứ hai của A với số đầu tiên của B.

Answer 2

Cung cấp số thứ nhất và số thứ hai trong các bộ dữ liệu luôn tăng dần (có vẻ như ví dụ của bạn) về nguyên tắc này không khác với regular LIS algorithm bên cạnh một số sửa đổi nhỏ: Chỉ cần tăng LIS tối đa lên đến tuple hiện tại mà số cuối cùng nhỏ hơn số đầu tiên của tuple hiện tại. Sử dụng lập trình động để cache LIS tối đa và tuple tiền nhiệm cho mỗi điểm chuỗi.

Answer 3

Bạn sẽ phải tìm ra LIS đầu tiên và sau đó tính toán cardinality của nó

Answer 4

Tôi nghĩ bạn có thể sử dụng thuật toán LIS chuẩn với ngoại lệ nhỏ -

khi so sánh chỉ mục i với chỉ số i + 1 - so sánh giá trị trên của i với giá trị thấp hơn của i + 1.

CHỈNH SỬA: Tất nhiên, điều này giả định rằng tất cả các phạm vi đều có số thấp hơn trước và số trên tiếp theo.

Answer 5

Mô hình vấn đề dưới dạng biểu đồ. Mỗi tuple có thể là một nút. Một cạnh đạo diễn tồn tại từ nút này sang nút khác nếu bộ đầu tiên nhỏ hơn giá trị thứ hai (ở đây "ít" nghĩa là cả hai giá trị của bộ dữ liệu đều ít hơn).

Các chuỗi tăng dài nhất bây giờ là con đường dài nhất trong biểu đồ này. Lưu ý rằng không có chu kỳ nào trong biểu đồ này (tức là nó là một DAG). Con đường dài nhất trong một DAG có thể được tìm thấy bằng lập trình động (xem wikipedia).

Answer 6

Tôi không chắc chắn bạn đang hỏi gì nhưng tôi sẽ giả định ý bạn là cặp (a, b) nhỏ hơn một cặp khác (c, d) nếu và chỉ khi < c và b < d .

Điều này có thể dễ dàng được giải quyết trong thời gian O (N^2) bằng cách điều chỉnh kỹ thuật lập trình động chuẩn, được mô tả in another SO thread.

Cổ điển O (N log N) solution to the standard LIS problem có thể được mở rộng để đưa ra giải pháp subquadratic cho vấn đề LIS theo cặp, với một số khó khăn. Chúng ta không thể đơn giản nhớ một giá trị tối thiểu cho mọi độ dài có thể; chúng ta phải duy trì các cấu trúc "giống như cầu thang" chứa tất cả các cặp tối thiểu cho mỗi chiều dài, nghĩa là, tối đa N bản sao của cấu trúc dữ liệu được mô tả here, được thực hiện bằng cách sử dụng một tập hợp các cặp năng động được đặt hàng khóa trên thành viên đầu tiên. Sau đó chúng ta có thể truy vấn một bản sao của cấu trúc này trong thời gian O (log N) (để kiểm tra xem nó có chứa bất kỳ cặp nào nhỏ hơn cặp hiện tại), cho thời gian O (log^2 N) cho bước tìm kiếm nhị phân, và O (N) đăng nhập^2 N) thời gian trong tất cả. Đây là giải pháp nhanh nhất mà tôi biết cho vấn đề.

Answer 7

Tiến hành như chúng tôi thực hiện trong trường hợp tìm LIS của mảng đơn giản. Ngay bên cạnh chỉ làm một so sánh, hãy so sánh cả hai phần tử. Nó sẽ cung cấp cho LIS với độ phức tạp thời gian O (n^2).