title: Obtaining the longest increasing subsequence in Python
body: <p>Can anyone tell me why this code doesn't produce each increasing subsequence?
  I used dynamic programming to solve this but I can't figure out why this code fails.
  The parameter <code>A</code> is a sequence of integers.</p>
  
  <pre><code>def LIS(A):
  
      # make a list of lists
      L = list()
      for i in range(0, len(A)):
          L.append(list())
  
      #the first increasing subsequence is the first element in A
      L[0].append(A[0])
  
      for i in range(1, len(A)):
          for j in (0, i):
  
              # a new larger increasing subsequence found
              if (A[j] &lt; A[i]) and ( len(L[i]) &lt; len(L[j]) ):
                  L[i] = L[j]
  
          L[i].append(A[i])
  
          # print an increasing subsequence
          print L[i]
  </code></pre>
  
  <p>Example output produced for A = [3, 5, 10, 0, 1, 100, 2, 4, 7] by this algorithm:</p>
  
  <pre><code>[3, 5]
  [3, 5, 10]
  [0]
  [1]
  [3, 5, 10, 100]
  [2]
  [3, 5, 10, 100, 4]
  [3, 5, 10, 100, 4, 7]
  None
  </code></pre>
  
  <p>Correct output:</p>
  
  <pre><code>[3] 
  [3, 5] 
  [3, 5, 10] 
  [0] 
  [0, 1] 
  [3, 5, 10, 100] 
  [0, 1, 2] 
  [0, 1, 2, 4] 
  [0, 1, 2, 4, 7] 
  </code></pre>