Längste Erhöhung der Untersequenz-Optimierung

Question

Die Längste zunehmende Untersequenz Problem ist es, eine Untersequenz einer gegebenen Sequenz zu finden, in der die Untersequenzelemente in sortierter Reihenfolge sind und in der die Untersequenz so lang wie möglich ist.

Hier ist mein O (n^2) Ansatz, der für lange Eingabe sehr langsam ausgeführt wird:

N = int(input()) 

lst = [] 
for i in range(N): 
    lst.append(input()) 

count = [1] * N 

for i in range(1, len(lst)): 
    for j in range(i): 
     if(int(lst[j]) < int(lst[i])): 
      k = int(count[j]) + 1 
      if (k > int(count[i])): 
       count[i] = k 
count.sort() 
print(count[-1]) 

Kann mir jemand sagen, wie es in O getan werden kann (n * log n) Zeit?

Answer 1

Große Ressourcen wurden in den Kommentaren erwähnt; Wenn Sie immer noch ein Stück Python-Code haben wollen, habe ich es hier geschrieben und erklärt.

In diesem Algorithmus, für alle L < N, verfolgen wir die Werte in der Eingabe, die den Endpunkt der aktuell am längsten wachsenden Untersequenz der Länge L darstellen.

longest_sequence_values speichert diese Werte. Zum Beispiel ist longest_sequence_values[3] ein Wert in der Eingabe, bei dem die am längsten zunehmende Untersequenz der Länge 3 endet.

Beachten Sie, dass longest_sequence_values immer nicht abnehmend ist, was uns erlaubt, eine binäre Suche durchzuführen, wenn wir versuchen, eine neue am längsten wachsende Untersequenz zu erstellen. Dies geschieht, weil der Endpunkt einer Untersequenz der Länge i nicht größer als der Endpunkt einer Untersequenz der Länge j sein kann, wenn i < j.

longest_current_sequence ist die Länge der längsten bisher gefundenen Teilsequenz. Wir benötigen diesen Wert, um den Bereich der binären Suche anzugeben. Es ist auch die Antwort am Ende.

from math import ceil 
N = int(input()) 

input_vals = [] 
for i in range(N): 
    input_vals.append(input()) 

longest_sequence_values = [None] * (N+1) 
longest_current_sequence = 0 

for i in range(N): 
    # binary search starts here 
    # this gives us the log(N) factor 
    lo = 1 
    hi = longest_current_sequence 
    while lo <= hi: 
     mid = int(ceil((lo+hi)/2)) 
     if longest_sequence_values[mid] <= input_vals[i]: 
      lo = mid + 1 
     else: 
      hi = mid - 1 

    # lo will be length of the longest sequence ending at input_vals[i] 
    longest_len_here = lo 
    # We have a new lis of length longest_len_here ending at index i 
    # Note that before we perform the following substitutions, 
    # longest_sequence_values[longest_len_here] >= input_vals[i] 
    # This means that the new endpoint of the lis of length longest_len_here 
    # is <= to the old endpoint. 
    # This point is essential in keeping the result optimal 
    longest_sequence_values[longest_len_here] = input_vals[i] 

    if longest_len_here > longest_current_sequence: 
     longest_current_sequence = longest_len_here 

print longest_current_sequence