Return to Answer

Note: some of the suggestions here concern the revised version of the code, that was posted as this other answer.

Note: some of the suggestions here concern the revised version of the code, that was posted as this other answer.

• You may consider renaming the function to include the full name.

• You may consider handling the empty sequence correctly.

• I think it is possible to have a better name for the head variable.

• Using None gives better readability to mark that there are no predecessors.

• In some applications, it may be beneficial to return indices instead of actual values.

def longest_increasing_subsequence(seq):
 if not seq: return seq
 
 lastoflength = [0] # end position of subsequence with given length
 predecessor = [None] # penultimate element of l.i.s. ending at given position
 for i in range(1, len(seq)):
 # seq[i] can extend a subsequence that ends with a smaller element
 j = bisect_left([seq[k] for k in lastoflength], seq[i])
 # update existing subsequence of length j or extend the longest
 try: lastoflength[j] = i
 except: lastoflength.append(i)
 # remember element before seq[i] in the subsequence
 predecessor.append(lastoflength[j-1] if j > 0 else None)
 # return indices ..., p(p(p(i))), p(p(i)), p(i), i
 indices = []
 i = lastoflength[-1]
 while i is not None:
 indices.append(i)
 i = predecessor[i]
 return indices[::-1]

• You may consider renaming the function to include the full name.

• You may consider handling the empty sequence correctly.

• I think it is possible to have a better name for the head variable.

• Using None gives better readability to mark that there are no predecessors.

• In some applications, it may be beneficial to return indices instead of actual values.

• It is possible to generate the indices in correct order directly, using recursion.

def longest_increasing_subsequence(seq):
 if not seq: return seq
 
 lastoflength = [0] # end position of subsequence with given length
 predecessor = [None] # penultimate element of l.i.s. ending at given position
 for i in range(1, len(seq)):
 # seq[i] can extend a subsequence that ends with a smaller element
 j = bisect_left([seq[k] for k in lastoflength], seq[i])
 # update existing subsequence of length j or extend the longest
 try: lastoflength[j] = i
 except: lastoflength.append(i)
 # remember element before seq[i] in the subsequence
 predecessor.append(lastoflength[j-1] if j > 0 else None)
 # return indices ..., p(p(p(i))), p(p(i)), p(i), i
 def trace(i):
 if i is not None:
  yield from trace(predecessor[i])
 yield i
 return list(trace(lastoflength[-1]))

Note: some of the suggestions here concern the revised version of the code, that was posted as this other answer .