# Memoized Palindrome Subsequence

I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following algorithm will work.Could also someone explain what the runtime will be?

Memoized-Palindrome(A,n)
initialize longest [i][j] =0 for all i and j
then return Memoized-Palindrome1(A,1,n,longest)

Memoized-Palindrome1(A,i,j,longest)
if longest[i][j]>0 return longest [i][j]
if (j-i) <=1 return j-i
if A[i]==A[j]
then longest[i][j] = 2 + Memoized-Palindrome1(A,i+1,j-1,longest)
else
longest[i][j]= max(Memoized-Palindrome1(A,i+1,j,longest),Memoized-Palindrome1(A,i,j+1,longest)
return longest[i][j]

-
Replace j+1 with j-1, also in the base case you should make a case analysis: if i == j and if j == i + 1 then you have to test whether A[i] == A[j]. – jmad Nov 12 '12 at 19:26
possible duplicate of How to come up with the runtime of algorithms? – D.W. Dec 4 '14 at 0:06

In dynamic programming, however, you usually write the order in which your function is called. (This is one key difference between them.) In this case, you will clearly see that you will compute $n$ longest[i][i] first, then $n-1$ longest[i][i+1], then $n-2$ longest[i][i+2] etc. each computation being in constant time. Giving a complexity of $n+(n-1)+\dots+2+1$=$n(n+1)/2$ i.e. $O(n^2)$.