I was solving a problem on LIS (Longest Increasing Subset) and I couldn't solve it completely. I googled for some solutions and on rosettacode I found several ones. I liked this one because it looks very short and straight forward (so easier to understand). But it's written in such a way that I am having serious troubles rewriting it.
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]]
)
This is the part I am having troubles to understand. This is what I think I understood:
append to the solutions array the longest combination of numbers in the solutions array, lower than the current number i am considering from the input array; plus the number you are considering from the input array. (Sorry for my English).
I feel like I didn't understand fully what the code is doing.
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)))
Let me expand out the code for you:
def longest_increasing_subsequence(d):
'Return one of the L.I.S. of list d'
l = []
for i in range(len(d)):
# currently the LIS is just this number
lis_at_this_index = [d[i]]
# for all the previous LIS
for j in range(i):
# if d[i] can be added to it and still be increasing
if l[j][-1] < d[i]:
# update the candidate LIS at this index
lis_at_this_index = max(lis_at_this_index, l[j] + [d[i]], key=len)
l.append(lis_at_this_index)
# return the global maximum
return max(l, key=len)
The idea is that if we have the LIS for indices [0..i-1], we can compute the LIS for index i like so:
And then you return the longest out of all the LIS at each index.