longest_increasing_subsequence_o_nlogn.py

#############################
# Author: Aravind Kashyap
# File: lis.py
# comments: This programme outputs the Longest Strictly Increasing Subsequence in
# O(NLogN) Where N is the Number of elements in the list
#############################
from __future__ importannotations


defceil_index(v, left, right, key):
whileright-left>1:
middle= (left+right) //2
ifv[middle] >=key:
right=middle
else:
left=middle
returnright


deflongest_increasing_subsequence_length(v: list[int]) ->int:
"""
 >>> longest_increasing_subsequence_length([2, 5, 3, 7, 11, 8, 10, 13, 6])
 6
 >>> longest_increasing_subsequence_length([])
 0
 >>> longest_increasing_subsequence_length([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13,
 ... 3, 11, 7, 15])
 6
 >>> longest_increasing_subsequence_length([5, 4, 3, 2, 1])
 1
 """
iflen(v) ==0:
return0

tail= [0] *len(v)
length=1

tail[0] =v[0]

foriinrange(1, len(v)):
ifv[i] <tail[0]:
tail[0] =v[i]
elifv[i] >tail[length-1]:
tail[length] =v[i]
length+=1
else:
tail[ceil_index(tail, -1, length-1, v[i])] =v[i]

returnlength


if__name__=="__main__":
importdoctest

doctest.testmod()