title: Largest Increasing SubSequence with O(n^2) using Recursions
body: <p>LIS :The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest</p>
  
  <p>Eg: </p>
  
  <blockquote>
    <p>0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 </p>
    
    <p>A longest increasing subsequence is 0, 2, 6, 9, 13, 15.</p>
  </blockquote>
  
  <p>I can develop LIS using different ways like Dynamic programming and memorization techniques but, with a particular case where I like to implement LIS using recursion with time complexity of <code>O(N^2)</code>.</p>
  
  <p>As of I think using recursion we cannot implement algorithms with time complexity <code>O(N^2)</code>.(Please correct me)</p>
  
  <p>However i got this algorithm from google</p>
  
  <pre><code>Algorithm  LIS(A,n,x)
  1: if n = 0 then
  2:   return 0
  3: m   LIS(A; n -1; x)
  4: if A[n] &lt; x then
  5:   m =max(m; 1 + LIS(A; n-1;A[n]))
  6: print(m)
  </code></pre>
  
  <p>Is this algorithm <code>O(N^2)</code>?</p>
  
  <p>Can you please explain?  </p>