Problem:


Longest Increasing Subsequence

For a given sequence A = {a0, a1, ... , an-1}, find the length of the longest increasing subsequnece (LIS) in A.

An increasing subsequence of A is defined by a subsequence {ai0, ai1, ... , aik} where 0 ≤ i0 < i1 < ... < ik < n and ai0 < ai1 < ... < aik.

Input

n
a0
a1
:
an-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 ≤ ai ≤ 109

Sample Input 1

5
5
1
3
2
4

Sample Output 1

3

Sample Input 2

3
1
1
1

Sample Output 2

1



Sample input:
5
5
1
3
2
4


Sample output:
3

Submission status: Accepted

Solution code:
# http://even-eko.hatenablog.com/entry/2013/09/05/215236
# https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5

import bisect

N = int(input())
Data = []
for _ in range(N):
    Data.append(int(input()))

LIS = []
LIS.append( Data[0] )

for i in range(1,N):
    n = Data[i]
    if n > LIS[-1]:
        LIS.append(n)
    else:
        p = bisect.bisect_left(LIS,n)
        LIS[p] = n

print(len(LIS))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math,bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n=int(input())
A=[int(input()) for i in range(n)]
dp=[inf]*(n+10)
dp[0]=A[0]
length=1
for i in range(1,n):
    if dp[length-1]<A[i]:
        dp[length]=A[i]
        length+=1
    else:
        # print(bisect.bisect_left(dp, A[i]),i)
        dp[bisect.bisect_left(dp,A[i])]=A[i]
print(length)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def main():
    n = int(input())
    a = [-1] * n
    for i in range(n):
        a[i] = int(input())

    ans = solve3(n, a)
    # print("ans={}".format(ans))
    print(ans)


def solve1(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n + 1)]
    for i in range(n):
        for j in range(1, i + 2):
            if j == 1 or a[i] > dp[j - 1]:
                dp[j] = min(dp[j], a[i])

    ret = 0
    for i in range(n + 1):
        if dp[i] < INF:
            ret = i
    return ret


def solve2(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n)]
    for i in range(n):
        for j in range(i + 2):
            if j == 0 or a[i] > dp[j - 1]:
                dp[j] = min(dp[j], a[i])
    ans = 0
    for i in range(n):
        if dp[i] < INF:
            ans = i + 1
    return ans


def solve3(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n)]
    for i in range(n):
        ix = bisect_left(dp, a[i])
        dp[ix] = a[i]
    ans = bisect_left(dp, INF)
    return ans


def solve4(n, a):
    INF = 10 ** 10
    dp = [INF for i in range(n)]
    for elt in a:
        ix = bisect_left(dp, elt)
        dp[ix] = elt

    ans = 0
    for i in range(n):
        if dp[i] < INF:
            ans = i + 1

    return ans


main()

Submission status: Accepted

Solution code:
import bisect


n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
L = []
L.append(a[0])
for i in range(1,n):
    p = bisect.bisect_right(L, a[i])
    if L[-1] == a[i]:
        continue;
    elif p == len(L):
        L.append(a[i])
    else:
        if L[p-1] != a[i]:
            L[p] = a[i]
print(len(L))

Submission status: Accepted

Solution code:
import bisect

def main():
    A = []
    length = 0
    
    for i in range(int(input())):
        a = int(input())
    
        idx = bisect.bisect_left(A, a)
        
        if idx == length:
            A.append(a)
            length += 1
            
        else: A[idx] = a
        
    print(length)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [10**9 + 1]

for i in range(N):
  target = int(input())
  target_idx = bisect.bisect_left(A, target)
  if target_idx > len(A) - 1:
    A.append(target)
  else:
    A[target_idx] = target

print(len(A))

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
N,*A=map(int,open(0))
r=[A[0]]+[1e9]*N
for a in A[1:]:i=bl(r,a);r[i]=min(r[i],a)
print(bl(r,1e9))

Submission status: Accepted

Solution code:
from sys import stdin

def interval(l, e):
    left = 0
    right = len(l)
    while left < right:
        mid = (left + right) // 2
        if l[mid] < e:
            left = mid + 1
        else:
            right = mid
    return left

def LIS(n, a):
    l = [a[0]]
    for e in a[1:]:
        if l[-1] < e:
            l.append(e)
        else:
            l[interval(l, e)] = e
    return len(l)


def main():
    n = int(input())
    a = list(map(int, stdin.readlines()))
    print(LIS(n, a))


main()

Submission status: Accepted

Solution code:
from bisect import bisect
import sys


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

    dp = [sys.maxsize] * (n + 1)
    dp[0] = -1

    for elem in a:
        idx = bisect(dp, elem - 1)
        dp[idx] = min(elem, dp[idx])

    ans = max(i for i in range(n + 1) if dp[i] < sys.maxsize)
    print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
C = [int(input())for _ in range(N)]
INF = float('inf')
dp = [INF]*N
max_ind = 0
for c in C:
    index = bisect.bisect_left(dp,c)
    dp[index] = c
    max_ind = max(max_ind,index)

print(max_ind+1)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
dp = [float('inf')]*n
for i in range(n):
    k = bisect.bisect_left(dp,L[i])
    dp[k] = L[i]
ans = 0
for i in range(n):
    if dp[i] != float('inf'):
        ans += 1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**10
memory = [INF for _ in range(N)]
ans = 0
def search(x):
  l = 0
  r = len(memory) - 1
  cp = (l + r) // 2
  while r - l >= 0:
    cp = (l + r) // 2
    if memory[cp] >= x:
      r = cp - 1
    else:
      l = cp + 1
  return l
ans = 0 
for a in A:
  point = search(a)
  memory[point] = a
  ans = max(ans, point)

print(ans + 1)

Submission status: Accepted

Solution code:
import  bisect
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

Ans=[-1]#0ではない

for i in range(n):
    #l=len(Ans)
    #for j in range(len(Ans)):
        #if i<j:
    #    if j!=l-1:
    #        if Ans[j]<a[i]<Ans[j+1]:
    #            Ans[j+1]=a[i]
                #print(*Ans)
    #    elif Ans[j]<a[i]:
    #        Ans.append(a[i])
    l=bisect.bisect_left(Ans,a[i])
    if l==len(Ans):
        Ans.append(a[i])
    else:
        Ans[l]=a[i]

#print(*Ans)

print(len(Ans)-1)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# DPL 1 D

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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import bisect

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

# last[m] == A[:i]中の長さmの増加部分列の末尾 (の最小値)
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import bisect
import sys

input=sys.stdin.readline

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

#A=[float('inf')*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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]
#print(dp)
cnt=0
for i in range(len(L)):
    if dp[i]<10**20:
        cnt+=1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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

from bisect import bisect_left as bl

for a in A: # i$BHVL\$NMWAG$r8+$k!!(B
    L_idx = bl(dp, a)
    dp[L_idx] = a

# print(dp)
print( bl(dp, inf)   )

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
a = []
INF = float('inf')
for i in range(n):
    aa = int(input())
    a.append(aa)
#dp[i][j] =a_0～a_iにおける長さjの部分増加列の最後の数のmin
#dp[i][j] = dp[i-1][j-1] < a[i]ならmin(a[i],dp[i-1][j])
#            そうでないならdp[i-1][j]

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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import bisect

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

# lis[n] = 最長増加部分列の長さがnであるものの最終要素の最小値
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_D: Combinatorial - Longest Increasing Subsequence


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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Runtime Error

Solution code:
import bisect
a = int(input())
b = [int(input()) in d in range(a)]
c = [b[1]]
for i in b[1:]:
    if c[-1] < i:
        c.append(i)
    else:
        c[bisect.bisect_left(c,i)] = i
        
print(len(L))

Submission status: Runtime Error

Solution code:
import bisect
a = int(input())
b = [int(input()) in d in range(a)]
c = [b[1]]
for i in b[1:]:
    if c[-1] < i:
        c.append(i)
    else:
        c[bisect.bisect_left(c,i)] = i
        
print(len(c))

Submission status: Runtime Error

Solution code:
import bisect

INF = 1 << 20


def main():
    n = int(input())
    a = [int(input()) for i in range(n)]

    dp = [INF for i in range(n+1)]
    for i in range(1, n+1):
        idx = bisect.bisect_left(dp, a[i-1])
        dp[idx] = a[i-1]

    ans = bisect.bisect_left(dp, INF)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
in_list = []
for i in range(n):
    in_list.append(list(map(int, input().split())))

matrices = [["0" for _ in range(n)] for _ in range(n)]

for i in range(n):
    inp = in_list[i]
    u = inp[0]
    k = inp[1]
    for j in range(k):
        m = inp[j+2]
        matrices[i][m-1] = "1"

for i in range(n):
    print(" ".join(matrices[i]))

Submission status: Runtime Error

Solution code:
from sys import stdin
import bisect
readline = stdin.readline

dp = [-float('inf')]
n = int(readline())
a = (int(readline()) for _ in range(n))
for ai in a:
    if dp[-1] < ai:
        dp.append(ai)
    else:
        dp[bisect.bisect(dp, ai)] = ai
print(len(dp) - 1)

Submission status: Runtime Error

Solution code:
import bisect
def lis(A):
    n = len(A)
    L = [0] * n
    L[0] = A[0]
    length = 1

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

    return length

n = int(raw_input())
a = [int(raw_input()) for i in xrange(n)]
print lis(a)

Submission status: Runtime Error

Solution code:
from bisect import *
n = input()
dp = [n+1]*(n+1)
dp[0] = -1
for i in xrange(n):
    a = input()
    idx = bisect(dp, a-1)
    dp[idx] = min(a, dp[idx])
print bisect(dp, n)-1

Submission status: Runtime Error

Solution code:
n = int(input())
array = [int(input()) for _ in range(n)]
dp = [0] * (max(array) + 1)

for a in array:
    dp[a] = max(dp[a], max(dp[:a]) + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
def dfs(index,prev,n,a,dp):
    if dp[index][prev] != -1:
        return dp[index][prev]

    if index==n:
        return 0

    if prev != -1 and a[prev]>=a[index]:
        return dfs(index+1,prev,n,a,dp)

    ren=max(dfs(index+1,prev,n,a,dp),dfs(index+1,index,n,a,dp)+1)
    dp[index][prev]=ren
    return ren

n=int(input())
a=[-1 for i in range(n)]

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


dp=[[-1 for i in range(n+1)] for j in range(n+1)]

sum=dfs(0,-1,n,a,dp)
if sum==0:
    print(1)
else:
    print(sum)

Submission status: Runtime Error

Solution code:
def _input(n):
    return [int(raw_input()) if i in xrange(n)]

def LIS(arr):
    arr = [0] + arr
    L = [0] + [0] * len(arr)
    P = [-1] + [0] * len(arr)

    for i in xrange(1, len(arr)):
        k = 0
        for j in xrange(0, i):
            if arr[j] < arr[i] and L[j] > L[k]:
                k = j
        L[i] = L[k] + 1
        P[i] = k

    return max(L)

#==============================================
def main():
    n = int(raw_input())
    arr = _input(n)
    print LIS(arr)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            L[j] = i
    return len(L)

print(LIS())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
L = [A[0]]

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

Submission status: Runtime Error

Solution code:
n = int(input())
parent = [-1]*n
def root(x):
	if parent[x] < 0:
		return x
	parent[x] = y = root(parent[x])
	return y
def union(x, y):
	px = root(x)
	py = root(y)
	if px == py:
		return
	if px > py:
		px = root(y)
		py = root(x)
	parent[x] += parent[y]
	parent[y] = px
	return
	
Q = []
for i in range(n):
	a = int(input())
	for j in range(i):
		if Q[-j-1] < a:
			union(Q[-j-1], a)
			continue
		continue
	Q += [a]
print(-min(parent))

Submission status: Runtime Error

Solution code:
n = int(input())
parent = [-1]*n
def root(x):
	if parent[x] < 0:
		return x
	parent[x] = y = root(parent[x])
	return y
def union(x, y):
	px = root(x)
	py = root(y)
	if px == py:
		return
	if px > py:
		px = root(y)
		py = root(x)
	parent[x] += parent[y]
	parent[y] = px
	return

Q = []
for i in range(n):
	a = int(input())
	for j in range(i):
		if Q[-j-1] < a:
			union(Q[-j-1], a)
			continue
	Q += [a]
print(-min(parent))


"""
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
L = [A[0]]
for a in A[1:]:
    if L[-1] < a:
        L.append(a)
    else:
        L[bisect.bisect_left(L, a)] = a
print(len(L))
"""

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int T;
int DS[1001];
int DP[1001][1001];

int f(int i,int backed){
    int &s = DP[i][backed];
    if(i==T)return s=0;
    else if(backed!=T && DS[i]<=DS[backed])return s=f(i+1,backed);
    else return s=max(1+f(i+1,i),f(i+1,backed));

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>T;
    memset(DP,-1,sizeof(DP));
    for(int i=0;i<T;++i){

        cin>>DS[i];

    }
    cout<<f(0,T)<<endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int T;
int DS[10001];
int DP[1001][1001];

int f(int i,int backed){
    int &s = DP[i][backed];
    if(i==T)return s=0;
    else if(s!=-1)return s;
    else if(backed!=T && DS[i]<=DS[backed])return s=f(i+1,backed);
    else return s=max(1+f(i+1,i),f(i+1,backed));

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>T;
    memset(DP,-1,sizeof(DP));
    for(int i=0;i<T;++i){

        cin>>DS[i];

    }
    cout<<f(0,T)<<endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int DP[100001];
int DS[100001];
int T;
int LIS(){
    int maxan=0;
    for(int k=0;k<T;k++){
        DP[k]=1;
        for(int i=0;i<k;i++){
            if(DS[i]<DS[k])DP[k]=max(DP[k],DP[i]+1);
        }
        maxan = max(maxan,DP[k]);
    }
    return maxan;





}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>T;

    for(int i=0;i<T;i++)cin>>DS[i];
    cout<<LIS()<<endl;





    return 0;
}