Jak znaleźć długość LIS za pomocą dwóch liczb. Na przykład [(1,2) (7,8) (3,4) (5,6)] W powyższej sekwencji tablicowej długość LIS wynosiłaby 3. tj. [(1,2) (3,4) (5,6)] Masz pomysł?Najdłuższy wzrost liczby (LIS) z dwoma numerami
Można użyć dowolnego algorithm dla standardowego LIS problem z dwoma zmianami:
A < B) musi porównać drugą liczbę A do pierwszego numeru B.Pod warunkiem, że pierwszy i drugi numer w krotek sami są zawsze rosnące (co wydaje się być w przypadku z przykładu) to w zasadzie nie powinny się różnić od regular LIS algorithm poza niewielkimi modyfikacjami: Wystarczy zwiększyć maksymalną LIS aż do aktualna krotka, dla której ostatnia liczba jest mniejsza od pierwszej liczby bieżącej krotki. Użyj programowania dynamicznego, aby buforować maksymalną wartość LIS i poprzednią krotkę dla każdego miejsca sekwencji.
Trzeba będzie znaleźć Lis, a potem obliczyć jego liczność
myślę, że można użyć standardowego algorytmu LIS z małym wyjątkiem, że -
jeśli porównać indeks i o indeksie i + 1 - porównaj górną wartość I z niższej wartości i + 1.
EDYCJA: Zakłada się oczywiście, że wszystkie zakresy mają niższą liczbę pierwszą, a górną liczbę następną.
Modeluj problem jako wykres. Każda krotka może być węzłem. Krawędź skierowana istnieje od jednego węzła do drugiego, jeśli pierwsza krotka jest ściśle mniejsza od drugiej (tutaj "mniej" oznacza, że obie wartości krotki są mniejsze).
Najdłuższy podciąg rosnący jest teraz najdłuższą ścieżką na tym wykresie. Zauważ, że na tym wykresie nie ma cykli (to jest DAG). Najdłuższą ścieżkę w DAG można znaleźć za pomocą programowania dynamicznego (patrz wikipedia).
nie jestem pewien, o co prosicie, ale zakładam, że to, co masz na myśli to, że para (a, b) jest mniejszy niż inne pary (c, d) wtedy i tylko wtedy, gdy < c i b < d .
Można to łatwo rozwiązać w czasie O (N^2), dostosowując standardową technikę programowania dynamicznego, która jest opisana jako in another SO thread.
Klasyczny O (N log N) solution to the standard LIS problem może zostać rozszerzony, aby dać podwokatowe rozwiązanie problemu LIS parami, z pewnymi trudnościami. Nie możemy po prostu zapamiętać jednej minimalnej wartości dla każdej możliwej długości; musimy utrzymywać struktury "przypominające klatkę schodową" zawierające wszystkie minimalne pary dla każdej długości, to znaczy aż do N kopii struktury danych opisanej here, zaimplementowanej przy użyciu uporządkowanego dynamicznego zestawu par zakodowanych na pierwszym członie. Możemy następnie wysłać zapytanie do jednej kopii tej struktury w czasie O (log N) (aby sprawdzić, czy zawiera ona parę par mniej niż bieżąca para), podając czas O (log^2 N) dla etapu wyszukiwania binarnego i O (N log^2 N) we wszystkich czasach. Jest to najszybsze rozwiązanie, jakie znam na problem.
Postępuj tak jak w przypadku wyszukiwania LIS prostej tablicy. Zaraz obok robienia tylko jednego porównania, porównaj oba elementy. Da to LIS ze złożonością czasu O (n^2).
Co jest mniej niż wyglądać? Czy (1, 5) <(2, 6)? Jeśli tak, zaznaczona odpowiedź poniżej nie będzie działać. –