Come trovare la lunghezza di LIS utilizzando due numeri. Ad esempio, [(1,2) (7,8) (3,4) (5,6)] Nella sequenza di array sopra riportata, la lunghezza di LIS sarebbe 3. ie, [(1,2) (3,4) (5,6)] Qualche idea?Longest Increasing Successive (LIS) con due numeri
è possibile utilizzare qualsiasi algorithm per lo standard LIS problem, con due modifiche:
A < B) ha la necessità di confrontare il secondo numero di A per il primo numero di B.Se il primo e il secondo numero nelle stesse tuple sono sempre in ordine crescente (che sembra essere il caso del tuo esempio), questo in linea di principio non dovrebbe essere diverso da regular LIS algorithm oltre ad alcune modifiche minori: basta aumentare la LIS massima fino a tupla corrente per cui l'ultimo numero è inferiore al primo numero della tupla corrente. Utilizzare la programmazione dinamica per memorizzare nella cache il massimo LIS e la tupla precedente per ogni punto della sequenza.
Si dovrà trovare il LIS e poi calcolare la sua cardinalità
Penso che si può utilizzare l'algoritmo LIS di serie con la piccola eccezione che -
quando si confronta indice i con indice i + 1 - confrontare il valore superiore di I con il valore più basso di i + 1.
MODIFICA: Si presume ovviamente che tutti gli intervalli abbiano il numero più basso prima e il numero successivo successivo.
Modella il problema come un grafico. Ogni tupla può essere un nodo. Un edge diretto esiste da un nodo ad un altro se la prima tupla è strettamente inferiore alla seconda (qui "meno" significa che entrambi i valori della tupla sono minori).
La sottosequenza crescente più lunga è ora il percorso più lungo in questo grafico. Si noti che non ci possono essere cicli in questo grafico (cioè è un DAG). Il percorso più lungo in un DAG può essere trovato mediante la programmazione dinamica (vedere wikipedia).
Non sono sicuro di cosa stai chiedendo, ma assumerò che cosa intendi che una coppia (a, b) è inferiore a un'altra coppia (c, d) se e solo se uno < c eb < .
Questo può essere facilmente risolto in tempo O (N^2) adattando la tecnica di programmazione dinamica standard, che è descritta in another SO thread.
Il classico O (N log N) solution to the standard LIS problem può essere esteso per dare una soluzione subquadratica al problema LIS con coppie, con qualche difficoltà. Non possiamo semplicemente ricordare un valore minimo per ogni lunghezza possibile; dobbiamo mantenere strutture "a scala" contenenti tutte le coppie minime per ogni lunghezza, ovvero fino a N copie della struttura dati descritta here, implementate utilizzando un insieme dinamico ordinato di coppie immesse sul primo membro. Possiamo quindi interrogare una copia di questa struttura in tempo O (log N) (per verificare se contiene una coppia inferiore alla coppia corrente), dando O (log^2 N) tempo per il passo di ricerca binario, e O (N log^2 N) tempo in tutto. Questa è la soluzione più veloce che conosca per il problema.
Procedere come nel caso di ricerca LIS di array semplice. Oltre a fare solo un confronto, confronta entrambi gli elementi. Darà a LIS la complessità del tempo O (n^2).
Che aspetto ha di meno? È (1, 5) <(2, 6)? In tal caso, la risposta contrassegnata di seguito non funzionerà. –