CareerCup

Use Suffix trees to do it in O(n)

check dis out...
stevekrenzel.com/articles/longest-palnidrome

I think a dynamic programming approach would work

d[i,j] = d[i+1,j-1] + 1 , when Str[i] == Str[j]
max(d[i,j-1],[i+1,j]) when Str[i] != Str[j]

Method 1: O(n^2)
Assuming odd length palindrome, assume each character as a center of the palindrome and move two pointers left and right.
Similarly for even length palindromes

int MaxPalin(char * str)
{
    //Assuming odd length palindrome
    char * up,* down,* ptr1,* ptr2;
    int maxlen=0;
    for(ptr1=str;*ptr1;ptr1++)
    {
        for(up=down=ptr1;up>=str&&down&&*up==*down;up--,down++);
        if(*down=='\0'&&up<str)
            return strlen(str);
        if(*down=='\0'||up<str&&down-up>maxlen)
            maxlen=down-up;
        else if(down-up+1>str)
             maxlen=down-up+1;
    }
   //assuming even length palindromes
    for(ptr1=str,ptr2=str+1;*ptr2;ptr1++,ptr2++)
    if(*ptr1==*ptr2)
    {
         for(up=ptr1,down=ptr2;up>=str&&*down&&*up==*down;up--,down++);
        if(*down=='\0'&&up<str)
            return strlen(str);
        if(*down=='\0'||up<str&&down-up>maxlen)
            maxlen=down-up;
        else if(down-up+1>str)
             maxlen=down-up+1;
       }
    return maxlen;               
}

Above method 1 had many errors which I updated but they are no longer there and I am not going to type them again :)
But the algo should be clear I suppose
Method 2: O(n)
Step1: Make Suffix tree of the string and its reverse O(n)
step2: Find the internal node representing longest string in the suffix tree that has its successors as leaf nodes from both the string. This longest sting is the Longest palindrome

Another O(n^2) method is to find the longest common substring between the string and its reverse.
step1: compute the longest suffixes of the strings
suffix[i,j]=suffix[i-1,j-1]+1 if str1[i]==str2[j]
=0 otherwise
maxlength palindrome = max(suffix[i,j]) for all 0<=i,j<n
to find the palindrome trace backward diagonally until suffix[i,j] are non zero

for e.g. ABRACECARCD
DCRACECARBA

suffix mat:
A B R A C E C A R C D
D 0 0 0 0 0 0 0 0 0 0 1
C 0 0 0 0 1 0 1 0 0 1 0
R 0 0 1 0 0 0 0 0 1 0 0
A 1 0 0 2 0 0 0 1 0 0 0
C 0 0 0 0 3 0 1 0 0 1 0
E 0 0 0 0 0 4 0 0 0 0 0
C 0 0 0 0 1 0 5 0 0 1 0
A 0 0 0 0 0 0 0 6 0 0 0
R 0 0 0 0 0 0 0 0 7 0 0
B ..................... so on
A

Hope its very clear

ABCDEYZYFEDCBA
ABCDEFYZYEDCBA

longest common substring is ABCDE or EDCBA
But the only palindrome is YZY

NA