This is hint: maximal substring-palindrome is maximal common substring of given string and reversed string => You can solve it for O(N^2).
The second variant - trivial dynamic. dp[l][r] = answer for substring from l to r. Sorry for my poor english(((

Edited by author 13.11.2012 23:38