def longest_increasing_subseq(seq):
 if (not seq):
  return []
 head = [0]
 predecessor = [(-1)]
 for i in range(1, len(seq)):
  j = bisect_left([seq[head[idx]] for idx in range(len(head))], seq[i])
  if (j == len(head)):
   head.append(i)
  if (seq[i] < seq[head[j]]):
   head[j] = i
  predecessor.append((head[(j - 1)] if (j > 0) else (-1)))
 result = []
 trace_idx = head[(-1)]
 while (trace_idx >= 0):
  result.append(seq[trace_idx])
  trace_idx = predecessor[trace_idx]
 return result[::(-1)]

def longest_increasing_subseq ( seq ) : if ( not seq ) : return [ ] head = [ 0 ] predecessor = [ ( - 1 ) ] for i in range ( 1 , len ( seq ) ) : j = bisect_left ( [ seq [ head [ idx ] ] for idx in range ( len ( head ) ) ] , seq [ i ] ) if ( j == len ( head ) ) : head . append ( i ) if ( seq [ i ] < seq [ head [ j ] ] ) : head [ j ] = i predecessor . append ( ( head [ ( j - 1 ) ] if ( j > 0 ) else ( - 1 ) ) ) result = [ ] trace_idx = head [ ( - 1 ) ] while ( trace_idx >= 0 ) : result . append ( seq [ trace_idx ] ) trace_idx = predecessor [ trace_idx ] return result [ : : ( - 1 ) ]
returns the longest subsequence of seq that is strictly increasing .