Anonymous user
Longest increasing subsequence: Difference between revisions
Fixed a bug with empty input, removed useless index, and better formatting for second Python entry
(Promote from draft to full task status) |
(Fixed a bug with empty input, removed useless index, and better formatting for second Python entry) |
||
Line 111:
<lang python>from collections import namedtuple
class
def __iter__(self):
while self is not None:
yield self.val
self = self.back
def lis(d):
pile = [[Node(d[0], None)]]
for di in d[1:]:
for j, pj in enumerate(pile):
if pj[-1].val > di:
pj.append(
break
else:
pile.append([
return [val for val in pile[-1][-1]] [::-1]
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, lis(d)))</lang>
| |||