np. „ccddcc” w ciągu „abaccddccefe”

Myślałem o rozwiązaniu, ale działa ono w czasie O (n ^ 2)

Algo 1:

Steps: To metoda brutalnej siły

Have 2 for loops
dla i = 1 do i mniej niż array.length -1
dla j = i + 1 do j mniej niż tablica. długość W ten sposób możesz uzyskać podciąg każdej możliwej kombinacji z tablicyPosiada funkcję palindromu, która sprawdza, czy ciąg znaków jest palindromemso dla każdego podłańcucha (i, j) wywołaj tę funkcję, jeśli jest palindromem, zapisz ją w zmiennej łańcuchowejJeśli znajdziesz następny podciąg palindromu i jeśli jest on większy niż bieżący, zastąp go bieżącym. Wreszcie twoja zmienna łańcuchowa będzie miała odpowiedź

Issues: 1. Ten algo działa w czasie O (n ^ 2).

Algo 2:

Odwróć ciąg i zapisz go w innej tablicy Teraz znajdź największy pasujący podciąg między obiema tablicami Ale to też działa w czasie O (n ^ 2)

Czy możecie sobie wyobrazić algo, które działa lepiej? Jeśli to możliwe, czas O (n)