title: How to find largest square of palindrome in a matrix
body: <p>I am trying to solve a problem where I am given a nXn square matrix of characters and I want to find out size of the largest palindrome square from this? The largest palindrome square is, a square with all rows and all columns as palindrome.</p>
  
  <p>For eg.
  Input</p>
  
  <pre><code>a g h j k
  s d g d j
  s e f e n
  a d g d h 
  r y d g s
  </code></pre>
  
  <p>The output will be:</p>
  
  <pre><code>3
  </code></pre>
  
  <p>corresponding to the middle square. I am thinking of dynamic programming solution but unable to formulate the recurrence relation. I am thinking the dimensions should be a(i,j,k) where i, j are the bottom-right of rectangle and k be the size of palindrome square. 
  Can someone help me with the recurrence relation for this problem?</p>
  
  <p>EDIT:</p>
  
  <p>n&lt;500, so I believe that I can't go beyond O(n^3).</p>