Longest increasing subsequence

Longest increasing subsequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Calculate and show here a longest increasing subsequence of the list:

$\{3,2,6,4,5,1\}$

And of the list:

$\{0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15\}$

Note that a list may have more than one subsequence that is of the maximum length.

Ref

1. Dynamic Programming #1: Longest Increasing Subsequence on Youtube

Python

<lang python>def longest_increasing_subsequence(d):

   'Return one of the L.I.S. of list d'
   l = []
   for i in range(len(d)):
       l.append(max([l[j] for j in range(i) if l[j][-1] < d[i]] or [[]], key=len) 
                 + [d[i]])
   return max(l, key=len)

if __name__ == '__main__':

   for d in [[3,2,6,4,5,1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
       print('a L.I.S. of %s is %s' % (d, longest_increasing_subsequence(d)))</lang>

Output:

a L.I.S. of [3, 2, 6, 4, 5, 1] is [3, 4, 5]
a L.I.S. of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] is [0, 4, 6, 9, 13, 15]