title: Iterative solution to finding Longest Increasing Subsequence using Python
body: <p>I am trying to implement an iterative solution for Longest Increasing Subsequence using bisect. My implementation is failing at some point. Help me fix it.</p>
  
  <p><strong>Implementation:</strong></p>
  
  <pre><code>from bisect import bisect
  
  def lis_iterative(seq):
      buff = []
      for n in seq:
          i = bisect(buff, n)
          if i == len(buff):
              buff.append(n)
          else:
              buff[i] = n
      return buff
  
  def main():
      seq = [43, 25, 6, 37, 27, 26, 7, 24, 457, 5, 22, 72]
      print lis_iterative(seq)
  
  main()
  </code></pre>
  
  <p><strong>Expected Output:</strong></p>
  
  <pre><code>[6, 7, 24, 457]
  </code></pre>
  
  <p><strong>Generated Output:</strong></p>
  
  <pre><code>[5, 7, 22, 72]
  </code></pre>