## 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[0][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”