def longestSubsequencePalindrome(a): n = len(a) solutions = [[0 for _ in range(n)] for _ in range(n)] # Any sequence has a shortest palindrome out-of-box: it's an individual # item, the palindrome with length = 1. So let's iterate over main # diagonal and set length = 1 for such items. for i in range(n): solutions[i][i] = 1 # Now we fill the higher diagonals one-by-one with solutions, reusing # partial solutions from the diagonals below. for offset in range(1, n): for i in range(0, n - offset): j = offset + i # At the very first iteration, we have an empty diagonal below # so in case of palindrome we've got to init with initial size # such as 2. if a[i] == a[j] and offset == 1: solutions[i][j] = 2 # That means elif a[i] == a[j]: solutions[i][j] = solutions[i + 1][j - 1] + 2 else: solutions[i][j] = max( [solutions[i][j - 1], solutions[i + 1][j]] ) # At the end, top right corner will contain the length of longest # palindrome. return solutions[0][n - 1] assert longestSubsequencePalindrome([1, 2, 4, 1]) == 3 assert longestSubsequencePalindrome([1, 2, 3, 2, 1]) == 5