wojtask
commented
2 years ago Czy można skorzystać z tego rozwiązania, aby uprościć pseudokod? https://leetcode.com/problems/longest-increasing-subsequence/discuss/74825/Short-Java-solution-using-DP-O(n-log-n)
"NNP" -> "najdłuższy niemalejący podciąg (w skrócie: NNP)" "nie-wprost" -> "nie wprost" usunąć "identycznej, jak w procedurze LIS-Length z poprzedniego zadania" "aktualnie znanego niemalejącego podciągu X" -> "niemalejącego podciągu fragmentu \langle x1, \dots, x{i-1}\rangle" Zmienić nazwę procedury na "LMIS-Length" "Procedura zwraca ... rozwiązaniu." -> "Procedura zwraca informacje służące do odtworzenia znalezionego NNP. Można go otrzymać (w odwrotnej kolejności) przez wypisanie $x{a[m]}$, a następnie $x{b[a[m]]}$, $x_{b[b[a[m]]}$ itd., dopóki indeks nie jest zerem. Następująca rekurencyjna procedura pozwala wypisać NNP we właściwej kolejności. \begin{codebox} \Procname{$\proc{Print-LMIS}(b,X,i)$} \li \If $b[i]>0$ \li \Then $\proc{Print-LMIS}(b,X,b[i])$ \End \li wypisz $x_i$ \end{codebox} Dysponując tablicą $b$ i wartością $a[m]$ wyznaczonymi dla danego ciągu $X$, możemy wypisać jego NNP, wywołując $\proc{Print-LMIS}(b,X,a[m])$." "5--16" -> "5--16 algorytmu LMIS-Length"