Problem:
Longest Increasing Subsequence For a given sequence A = {a 0 , a 1 , ... , a n-1 } , find the length of the longest increasing subsequnece (LIS) in A . An increasing subsequence of A is defined by a subsequence {a i 0 , a i 1 , ... , a i k } where 0 ≤ i 0 < i 1 < ... < i k < n and a i 0 < a i 1 < ... < a i k . Input  n  a 0  a 1 : a n-1   In the first line, an integer n is given. In the next n lines, elements of A are given. Output The length of the longest increasing subsequence of A . Constraints  1 ≤ n ≤ 100000  0 ≤ a i ≤ 10 9  Sample Input 1 5
5
1
3
2
4 Sample Output 1 3 Sample Input 2 3
1
1
1 Sample Output 2 1

Solution (Python):
from bisect import *
import sys

def solve(N, A):
    INF = 10**10

    dp = [INF]*(N+1)
    dp[0] = -1
    for a in A:
        idx = bisect(dp, a-1)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

N, *A = map(int, sys.stdin.read().split())
sys.stdout.write("%d\n" % solve(N, A))

Solution (Python):


import bisect

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    dp = []
    dp.append(a[0])
    for i in range(1, n):
        if a[i] > dp[-1]:
            dp.append(a[i])
        else:
            j = bisect.bisect_left(dp, a[i])
            dp[j] = a[i]

    print(len(dp))


if __name__ == "__main__":
    solve()

Solution (Python):
import bisect
n = int(input())
dp=[int(input())]
for i in range(n-1):
    a = int(input())
    if dp[-1] < a:
        dp.append(a)
    else:
        dp[bisect.bisect_left(dp, a)] = a
print(len(dp))

Solution (Python):
from bisect import bisect_left


def main():
    n = int(input())
    lst = [int(input()) for _ in range(n)]
    print(lis(lst))


def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            L.append(a)
        else:
            L[bisect_left(L, a)] = a
    return len(L)


if __name__ == '__main__':
    main()

Solution (Python):


import bisect

n = int(input())
A = [int(input()) for _ in range(n)]


last = [-1]

for a in A:
    m = bisect.bisect_left(last, a)
    if m >= len(last):
        last.append(a)
    else:
        last[m] = min(last[m], a)

print(len(last) - 1)

Solution (Python):
from bisect import bisect_left

a = [int(input()) for _ in range(int(input()))]
LIS = [a[0]]

for i, x in enumerate(a):
    if LIS[-1] < x:
        LIS.append(x)
    else:
        LIS[bisect_left(LIS, x)] = x

print(len(LIS))

Solution (Python):
import bisect
import sys

input=sys.stdin.readline

n=int(input())
a=[int(input()) for _ in range(n)]



A=[float('inf')]

for i in range(n):
    if a[i]>A[-1]:
        A.append(a[i])
    else:
        idx=bisect.bisect_left(A,a[i])
        A[idx]=a[i]

print(len(A))

Solution (Python):
import bisect

N=int(input())
A=[int(input()) for i in range(N)]

DP=[float("inf")]*N

for a in A:
    pos=bisect.bisect_left(DP,a)
    DP[pos]=a

ANS=0
for i in range(N):
    if DP[i]!=float("inf"):
        ANS=i

print(ANS+1)

Solution (Python):


import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
A=[INT() for i in range(N)]

B=[A[0]]
for i in range(1, N):
    if A[i]>B[-1]:
        B.append(A[i])
    else:
        B[bisect_left(B, A[i])]=A[i]
print(len(B))

Solution (Python):
def binarysearch(lis,i,j,n):
    if lis[-1]<n:
        return len(lis)
    elif j-i == 1:
        return j
    else:
        m = (i+j)//2
        if lis[m] < n:
            return binarysearch(lis,m,j,n)
        elif lis[m]>n:
            return binarysearch(lis,i,m,n)
        elif lis[m] == n:
            return m


n = int(input())
lis = [-1]
for _ in range(n):
    x = int(input())
    y = len(lis)-1
    j = binarysearch(lis,0,y,x)
    if j == len(lis):
        lis.append(x)
    else:
        if lis[j] > x:
            lis[j] = x
print(len(lis)-1)

Solution (Python):
from bisect import bisect_left
length = int(input())
target = []
for _ in range(length):
    target.append(int(input()))
lis = [target[0]]
for t in target[1:]:
    if t > lis[-1]:
        lis.append(t)
    else:
        lis[bisect_left(lis, t)] = t
print(len(lis))

Solution (Python):
import bisect
N=int(input())

L=[]
for i in range(N):
    n=int(input())
    L.append(n)
    
dp=[10**20 for i in range(N)]
dp[0]=L[0]
for i in range(1,len(L)):
    dp[bisect.bisect_left(dp,L[i])]=L[i]

cnt=0
for i in range(len(L)):
    if dp[i]<10**20:
        cnt+=1
    else:
        break
print(cnt)

Solution (Python):
from bisect import bisect_left

n = int(input())
a = []
for _ in range(n):
    a += [int(input())]

def lis(A):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            L.append(a)
        else:
            L[bisect_left(L,a)] = a
    return len(L)
print(lis(a))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
l = [0]*n

li = 0
l[0] = a[0]
for i in range(1, n):
    if a[i] > l[li]:
        li += 1
        l[li] = a[i]
    else:
        j = bisect.bisect_left(l[:li], a[i])
        l[j] = a[i]
print(li+1)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

inf = float("inf")
dp = [inf] * (N+1)


from bisect import bisect_left as bl

for a in A: 
    L_idx = bl(dp, a)
    dp[L_idx] = a


print( bl(dp, inf)   )

Solution (Python):
import bisect
A=int(input())
ai=[]
for i in range(A):
    ai.append(int(input()))
min_num=[ai[0],float("inf")]
len_mn=2
for i in ai[1:]:
    b=bisect.bisect_left(min_num,i)
    if b==0:
        min_num[0]=i
    elif b+1==len_mn:
        min_num.insert(-1,i)
        len_mn+=1
    else:
        min_num[b]=i
print(len(min_num)-1)

Solution (Python):
import bisect

n=int(input())
a = []
INF = float('inf')
for i in range(n):
    aa = int(input())
    a.append(aa)




dp = [INF for i in range(n)]
dp[0] = a[0]
for i in range(1,n):
        p = bisect.bisect_left(dp, a[i])
        dp[p] = min(a[i],dp[p])

print(bisect.bisect_left(dp, INF))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
a=[int(input()) for i in range(int(input()))]
import bisect
LIS = [a[0]]
for i in range(len(a)):
    if a[i]>LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_left(LIS,a[i])] = a[i]
print(len(LIS))

Solution (Python):
import bisect

inf = 1 << 60
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))


lis = [A[0]]

for a in A:
    if lis[-1] < a:
        lis.append(a)
    else:
        lis[bisect.bisect_left(lis, a)] = a

print(len(lis))

Solution (Python):
import bisect


n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
    
longest = [0]
longest[0] = a[0]
for i in range(1, n):
    if longest[-1] < a[i]:
        longest.append(a[i])
    else:
        j = bisect.bisect_right(longest, a[i])
        if longest[j-1] == a[i]:
            longest[j-1] == a[i]
        else:
            longest[j] = a[i]

print(len(longest))

Solution (Python):
from bisect import bisect_left as bl
INF = 10 ** 10
n = int(input())
alst = [int(input()) for _ in range(n)]
dp = [INF] * (n + 1)
dp[0] = -1
ans = 0
for a in alst:
  ind = bl(dp, a)
  dp[ind] = a
  ans = max(ans, ind)
print(ans)

Solution (Python):




class SegmentTree:
    def __init__(self, n):
        size = 2**n.bit_length()
        self.size = 2*size - 1
        self.data = [0] * self.size

    def max(self, lo, hi):
        def _max(r, i, j):
            if j < lo or i > hi:
                return 0
            elif lo <= i and j <= hi:
                return self.data[r]
            else:
                mid = (i + j) // 2
                return max(_max(r*2+1, i, mid), _max(r*2+2, mid+1, j))

        return _max(0, 0, self.size//2)

    def set(self, i, v):
        r = self.size//2 + i
        self.data[r] = v
        while r > 0:
            r = (r-1) // 2
            self.data[r] = max(self.data[r*2 + 1], self.data[r*2 + 2])


def longest_increasing_subseq(vs):
    index = {v: i for i, v in enumerate(sorted(set(vs)))}
    seg = SegmentTree(len(index))
    c = 1

    for i in range(len(vs)):
        j = index[vs[i]]
        _c = seg.max(0, j-1)+1
        if _c > c:
            c = _c
        seg.set(j, _c)

    return c


def run():
    n = int(input())
    vs = []

    for _ in range(n):
        vs.append(int(input()))

    print(longest_increasing_subseq(vs))


if __name__ == '__main__':
    run()

Solution (Python):
import bisect

n = int(input())
a_list = [int(input()) for i in range(n)]


def lis(n, A):
    L = [0 for i in range(n + 1)]
    L[0] = A[0]
    length = 1
    for i in range(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            index = bisect.bisect_left(L, A[i], 0, length - 1)
            L[index] = A[i]
    return length


print(lis(n, a_list))

Solution (Python):
import bisect
n = int(input())
A =[]


for i in range(n):
  A.append(int(input()))

L = [A[0]]

for i in A:
  if L[-1] < i:
    L.append(i)
  else:
    L[bisect.bisect_left(L, i)] = i

print(len(L))

Solution (Python):
from bisect import bisect_left
n = int(input())
A = [int(input()) for i in range(n)]
L = [A[0]]
a = A[0]
for i in A[1:]:
    if L[-1] < i:
        L.append(i)
    else:
        L[bisect_left(L, i)] = i
    a = i
print(len(L))

Solution (Python):
def LIS(n, a):
	lis = 0
	dp = [0] * n
	dp[0] = a[0]
	for i in range(1, n):
		cur = a[i]
		if cur < dp[0]:
			dp[0] = cur
		elif cur > dp[lis]:
			lis += 1
			dp[lis] = cur
		else:
			idx = find_pos(cur,0,lis,dp)
			dp[idx] = cur
	return lis + 1

def find_pos(target, floor, ceiling, dp):
	while floor < ceiling:
		guess_idx = int(floor+(ceiling-floor)/2)
		guess_val = dp[guess_idx]
		if guess_val == target:
			return guess_idx
		if guess_val < target:
			floor = guess_idx + 1
		else:
			ceiling = guess_idx - 1
	if dp[floor] < target:
		return floor + 1
	return floor

n = int(input())
a = [0] * n
for i in range(n):
	a[i] = int(input())
print(LIS(n, a))

Solution (Python):
def LIS(L):
    from bisect import bisect
    seq=[L[0]]
    for i in L:
        pos=bisect(seq,i)
        if (seq[-1] < i):
            seq.append(i)
        elif(i not in seq):
            seq[pos]=i
    return len(seq)
n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
print(LIS(L))

Solution (Python):
import bisect

def lis(n, a):
    l = []
    l.append(a[0])
    length = 1
    for i in range(1, n):
        if l[length - 1] < a[i]:
            l.append(a[i])
            length += 1
        else:
            l[bisect.bisect_left(l, a[i], lo=0, hi=length)] = a[i]

    return length

if __name__ == '__main__':
    n = int(input())
    a = [int(input()) for i in range(n)]

    print(lis(n, a))

Solution (Python):
from bisect import bisect_left
alen=int(input())
ans=[int(input())]
for i in range(alen-1):
    n=int(input())
    if n>ans[-1]:
        ans.append(n)
    else:
        ans[bisect_left(ans,n)]=n
print(len(ans))

Solution (Python):
import bisect
n = int(input())
seq = [int(input()) for i in range(n)]

LIS = []
for number in seq:
    index = bisect.bisect_left(LIS, number)
    if index >= len(LIS):
       LIS.append(number)
    else:
        LIS[index] = number
print(len(LIS))