Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

initialize longest [i][j] =0 for all i and j
then return Memoized-Palindrome1(A,1,n,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)
      longest[i][j]= max(Memoized-Palindrome1(A,i+1,j,longest),Memoized-Palindrome1(A,i,j+1,longest)
return longest[i][j]
share|cite|improve this question
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
up vote 1 down vote accepted

This kind of approach is more often called dynamic programming than memoization but they are, indeed, related.

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)$.

share|cite|improve this answer
but One can say that the memoization belongs to dynamic programming, right? I think that is a top-down case of dp. – jonaprieto Nov 12 '12 at 20:50
@d555: not really: if dynamic programming could be seen as an example of memoization, the contrary is awkward. But even then, the techniques used are so different that dynamic programming algorithms are usually not qualified memoized. – jmad Nov 12 '12 at 21:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.