Da się łatwo w sześciennym, dla każdego \(\displaystyle{ i}\) robimy dwa ciągi rozcinając wejście w indeksie \(\displaystyle{ i}\). Następnie dla tych dwóch ciągów obliczamy długość najdłuższego wspólnego podciągu i z tego obliczamy ostateczny wynik.
Mam wrażenie, że dałoby się to przyspieszyć tak, aby nie liczyć przy zmianie \(\displaystyle{ i}\) całych tablic od nowa, ale jeszcze nie wiem jak.
Poza tym moją pierwszą myślą było wyszukiwanie binarne. Gdybyśmy potrafili odpowiedzieć w czasie kwadratowym, czy da się zrobić zająknięcie długości \(\displaystyle{ k}\), to pozostaje tylko binarnie znaleźć wynik, ale nie wiem jeszcze, jak to sprawdzić.