dynamic programming - Obtaining the longest increasing subsequence in Python -

can tell me why code doesn't produce each increasing subsequence? used dynamic programming solve can't figure out why code fails. parameter a sequence of integers.

def lis(a):      # make list of lists     l = list()     in range(0, len(a)):         l.append(list())      #the first increasing subsequence first element in     l[0].append(a[0])      in range(1, len(a)):         j in (0, i):              # new larger increasing subsequence found             if (a[j] < a[i]) , ( len(l[i]) < len(l[j]) ):                 l[i] = l[j]          l[i].append(a[i])          # print increasing subsequence         print l[i] 

example output produced = [3, 5, 10, 0, 1, 100, 2, 4, 7] algorithm:

[3, 5] [3, 5, 10] [0] [1] [3, 5, 10, 100] [2] [3, 5, 10, 100, 4] [3, 5, 10, 100, 4, 7] none 

correct output:

[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]  

two mistakes found in code

1.you assumed list immutable not in python

l[i] = l[j] going make l[i] point same list pointed l[j]  2.for j in (0, i): 

this not iterate j form 0 i-1 iterates j form 0 i.

here fixed version of code.

def lis(a):      # make list of lists     l = list()     in range(0, len(a)):         l.append(list())      # first increasing subsequence first element in     l[0].append(a[0])      in range(1, len(a)):         j in range(0, i):              # new larger increasing subsequence found             if (a[j] < a[i]) , (len(l[i]) < len(l[j])):                 'throw previous list'                 l[i] = []                 'add elements of l[j] l[i]'                 l[i].extend(l[j])         l[i].append(a[i])      in range(len(a)):     # print increasing subsequence         print (l[i]) = [3, 5, 10, 0, 1, 100, 2, 4, 7] lis(a)