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(((
