Нахождение самой длинной последовательности палиндрома с меньшим количеством памяти

Я пытаюсь решить задачу по динамическому программированию из Введение в алгоритмы 3-е издание (стр. 405) Кормчего, в которой спрашивается следующее:

Палиндром - это непустая строка над ... некоторого алфавита, которая читается одинаково как вперед, так и назад. Примерами палиндромов являются все строки длины 1, civic, racecar, и aibohphobia (боязнь палиндромов).

Дайте эффективный алгоритм для нахождения самого длинного палиндрома, который является подпоследовательностью заданной входной строки. Например, при вводе character, ваш алгоритм должен return carac.

Ну, я могу решить это двумя способами:

Первое решение:

Самая длинная палиндромная последовательность (LPS) строки - это просто самая длинная общая последовательность ее самой и ее обратной части. (Я построил это решение после решения другого связанного вопроса, в котором спрашивается Длиннейшая возрастающая последовательность последовательности). Поскольку это просто вариант LCS, он также требует O(n²) времени и O(n²) памяти.

Второе решение:

Второе решение немного более сложное, но также следует общему шаблону LCS. Оно вытекает из следующего рекуррента:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

Псевдокод для вычисления длины lps следующий:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

Это все еще требует O(n²) времени и памяти, если я хочу эффективно построить lps (потому что мне понадобятся все ячейки таблицы). Анализируя смежные задачи, такие как LIS, которые могут быть решены с помощью подходов, отличных от LCS-подобных, с меньшей памятью (LIS решаема с O(n) памятью), мне стало интересно, возможно ли решить ее также с O(n) памятью.

LIS достигает этой границы, связывая подпоследовательности кандидатов, но с палиндромами это сложнее, потому что здесь важен не предыдущий элемент в подпоследовательности, а первый. Кто-нибудь знает, возможно ли это сделать, или предыдущие решения оптимальны по памяти?