title: Why we cannot solve Longest Palindrome Subsequence by Divide and Conquer?
body: <p>Given an array string, find the longest substring which is palindrome. For example, if the given string is “forgeeksskeegfor”, the output should be "geeksskeeg".</p>
  
  <p>The problem has an efficient solution with Dynamic Programming.</p>
  
  <p>However, I was just wondering why cant we solve the problem with Divide and Conquer in a similar way we solve the Maximum Subarray problem. (<a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow">http://en.wikipedia.org/wiki/Maximum_subarray_problem</a> )</p>
  
  <p>We formulate the maximum subarray problem to be efficiently solved with D&amp;C:</p>
  
  <p>1) Divide the given array in two halves
  2) Return the maximum of following three
  ….a) Maximum subarray sum in left half (Make a recursive call)
  ….b) Maximum subarray sum in right half (Make a recursive call)
  ….c) Maximum subarray sum such that the subarray crosses the midpoint</p>
  
  <p>The longest Palindrome subsequence problem can be though of as :</p>
  
  <p>1) Divide the given array in two halves
  2) Return the maximum of following three
  ….a) Maximum palindrome sum in left half (Make a recursive call)
  ….b) Maximum palindrome sum in right half (Make a recursive call)
  ….c) Maximum palindrome sum such that the subarray crosses the midpoint</p>
  
  <p>We could think about an implementation and say a solution does not exists,but what about the problem structure stops us from thinking a D&amp;C solution? </p>