Longest Palindromic Subsequence

Thoughts:
Brute force solution, O(N^3):
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).

Since verifying each substring takes O(N) time, the run time complexity is O(N3).

Dynamic programming solution, O(N^2) time and O(N^2) space:
To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes.
Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore, P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:
P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

public static int lenOfMaxPalindrome(char[] a){
public static int lenOfMaxPalindrome(char[] a){
int n = a.length;
int[][] table = new int[n][n];

for(int i=0; i<n; i++){
table[i][i] = 1; //when len=1
}

//len is length of substring
for(int len=2; len<=n; len++){
//the start position of substring
for(int i=0; i<=n-len; i++){
int j = i+len-1;//the end position of substring
if(a[i] == a[j]){
if(len == 2){
table[i][j] = 2;
}else{
table[i][j] = table[i+1][j-1] + 2; //the element on down-left
}
}else{
table[i][j] = max(table[i][j-1], table[i+1][j]);
}
}
}

return table[n-1];
}

public static int max(int i, int j){
return i>j? i: j;
}

Time Complexity: O(n^2)

For example:
String is “abacba”       