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:
from sys import stdin
from bisect import bisect_left
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_left(dp, ai)] = ai
print(len(dp) - 1)

Submission status: Accepted

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[:length], A[i])] = A[i]

    return length

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

Submission status: Accepted

Solution code:
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.bisect_left(L, A[i])] = A[i]
print(len(L))

Submission status: Accepted

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

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import bisect
#D2
n = int(input())
a = [int(input()) for j in range(n)]

dp = [a[0]]
for i in range(1,n):
    if dp[-1] < a[i]:
        dp.append(a[i])
        #print(0,dp)

    else:
        dp[bisect.bisect_left(dp, a[i])] = a[i]
        #print(1,bisect.bisect_left(dp, a[i]),dp)
print(len(dp))

Submission status: Accepted

Solution code:
import bisect
n=input()
a=[input() for i in xrange(n)]
dp=[float('inf') for _ in xrange(n)]
for i in xrange(n):
    dp[bisect.bisect_left(dp,a[i])]=a[i]
for i in xrange(n):
    if dp[i]==float('inf'):
        i-=1
        break
print(i+1)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))

lis = [numbers[0]]
for last in numbers[1:]:
    if lis[-1] < last:
        lis.append(last)
    else:
        pos = bisect.bisect_left(lis, last)
        lis[pos] = last

print(len(lis))

Submission status: Accepted

Solution code:
from bisect import *
n = input()
dp = [10**10]*(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, 10**10-1)-1

Submission status: Accepted

Solution code:
from bisect import bisect_left

SENTINEL = 1e9 + 1
n = int(input())
dp = [SENTINEL] * n

for _ in range(n):
    a = int(input())
    dp[bisect_left(dp, a)] = a

print(bisect_left(dp, SENTINEL))

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
dp = [int(1e9) + 1] * n
eol = 0

for _ in range(n):
    a = int(input())
    if dp[eol] < a:
        eol += 1
        dp[eol] = a
    else:
        dp[bisect_left(dp, a, hi=eol)] = a

print(eol + 1)

Submission status: Accepted

Solution code:
import bisect
num = int(input())
targ = []
for n in range(num):
    targ.append(int(input()))
ans = []
for n in range(num):

    if ans == []:
        ans.append(targ[n])
    elif ans[-1] < targ[n]:
        ans.append(targ[n])
    else:
        ans[bisect.bisect_left(ans,targ[n])] = targ[n]
print(len(ans))

Submission status: Accepted

Solution code:
import bisect as bi

N = int(input())
c = [int(input()) for i in range(N)]
inf = 10000000000
lis = [inf for i in range(N)]

for i in range(N):
	lis[bi.bisect_left(lis, c[i])] = c[i]
	
print(bi.bisect_left(lis, inf))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
5
1
3
2
4

or

3
1
1
1

output:
3

or

1
"""

import sys
from bisect import bisect_left


def solve():
    dis_rec = [float('inf')] * array_length
    dis_rec[0] = array[0]
    length = 1
    for j in range(1, array_length):
        if dis_rec[length - 1] < array[j]:
            dis_rec[length] = array[j]
            length += 1
        else:
            position = bisect_left(dis_rec, array[j])
            dis_rec[position] = array[j]
    return length


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1:]))
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
5
1
3
2
4

or

3
1
1
1

output:
3

or

1
"""

import sys
from bisect import bisect_left


def solve():
    dis_rec = [float('inf')] * array_length
    dis_rec[0] = array[0]
    length = 1
 
    for i, ele in enumerate(array, 1):
        if dis_rec[length - 1] < ele:
            dis_rec[length] = ele
            length += 1
        else:
            position = bisect_left(dis_rec, ele)
            dis_rec[position] = ele

    return length


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1:]))
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
5
1
3
2
4

or

3
1
1
1

output:
3

or

1
"""

import sys
from bisect import bisect_left


def solve():
    dis_rec = [float('inf')] * array_length
    dis_rec[0] = array[0]
    length = 1
 
    for ele in array:
        if dis_rec[length - 1] < ele:
            dis_rec[length] = ele
            length += 1
        else:
            position = bisect_left(dis_rec, ele)
            dis_rec[position] = ele

    return length


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1:]))
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
8
4
1
6
2
8
5
7
3

or

3
1
1
1

output:
4

or

1
"""

import sys
from bisect import bisect_left


def solve():
    dis_rec = [float('inf')] * array_length
    dis_rec[0] = array[0]
    length = 1

    for ele in array:
        if dis_rec[length - 1] < ele:
            dis_rec[length] = ele
            length += 1
        else:
            position = bisect_left(dis_rec, ele)
            dis_rec[position] = ele

    # display DIS
    # print(*dis_rec[:length])
    return length


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1:]))
    print(solve())

Submission status: Accepted

Solution code:
import sys
import bisect

inf = float('inf')

def solve():
    n = int(input())
    A = [int(input()) for i in range(n)]
    dp = [-1] + [inf] * n
    max_ = 1

    for a in A:
        j = bisect.bisect_left(dp, a, lo=0, hi=max_)
        max_ = max(max_, j + 1)
        dp[j] = a

    # print(dp)
    ans = max_ - 1
    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import bisect

inf = float('inf')

def solve():
    n = int(input())
    A = [int(input()) for i in range(n)]
    dp = [inf] * n
    max_ = 1

    for a in A:
        j = bisect.bisect_left(dp, a, lo=0, hi=max_)
        max_ = max(max_, j + 1)
        dp[j] = a

    # print(dp)
    ans = max_
    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import bisect

inf = float('inf')

def solve():
    n = int(input())
    A = [int(input()) for i in range(n)]
    dp = [inf] * n
    # max_ = 1

    for a in A:
        j = bisect.bisect_left(dp, a)
        # max_ = max(max_, j + 1)
        dp[j] = a

    # print(dp)

    ans = 1
    for i, v in enumerate(dp):
        if v == inf:
            ans = i
            break
    else:
        ans = n
        
    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

def solve():
    n = int(input())
    A = [int(input()) for i in range(n)]

    inf = 10**9 + 1
    dp = [inf] * n

    for a in A:
        j = bisect_left(dp, a)
        dp[j] = a

    for i, v in enumerate(dp):
        if v == inf:
            print(i)
            return

    print(n)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
from bisect import bisect_left

def solve():
    n = int(stdin.readline())
    A = [int(stdin.readline()) for i in range(n)]

    inf = 10**9 + 1
    dp = [inf] * n

    for a in A:
        j = bisect_left(dp, a)
        dp[j] = a

    for i, v in enumerate(dp):
        if v == inf:
            print(i)
            return

    print(n)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin

def solve():
    n = int(stdin.readline())
    A = [int(stdin.readline()) for i in range(n)]

    inf = 10**9 + 1
    dp = [inf] * n

    for a in A:
        j = nibutan(dp, a)
        dp[j] = a

    for i, v in enumerate(dp):
        if v == inf:
            print(i)
            return

    print(n)

def nibutan(dp, a):
    btm = -1
    top = len(dp)

    while top - btm > 1:
        mid = (top + btm) // 2
        if dp[mid] >= a:
            top = mid
        else:
            btm = mid

    assert 0 <= top < len(dp)
    return top

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import bisect

def _input(n):
    return [int(raw_input()) for i in xrange(n)]

# Wrapper for built-in function
def lower_bound(arr, target):
    return bisect.bisect_right(arr, target)


def LIS(arr, n):
    L = [0] * n

    L[0] = arr[0]
    length = 1

    for i in xrange(1, n):
        if L[length - 1] < arr[i]:
            L[length] = arr[i]#L.append(A[i])
            length += 1
        else:
            if L[lower_bound(L[:length], arr[i])-1 if lower_bound(L[:length], arr[i])-1 > 0 else 0] \
                    != arr[i]: # Fix common item - Dont insert common item and zero Problem
                L[lower_bound(L[:length], arr[i])] = arr[i]
    return length, L

#=========================================================
def main():

    n = int(raw_input())
    arr = _input(n)
    print LIS(arr, n)[0]#, LIS(arr, n)[1]#, arr

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import bisect


def solve(N, a):
    dp = [float("inf")] * N
    for i in range(N):
        ins_p = bisect.bisect_left(dp, a[i])
        if dp[ins_p] != a[i]:
            dp[ins_p] = a[i]
    # sys.stderr.write(str(dp) + "\n")
    for i in range(N):
        if dp[i] == float("inf"):
            return i
    return N


def main():
    N = int(input())
    a = [None] * N
    for i in range(N):
        a[i] = int(input())

    print(solve(N, a))


main()

Submission status: Accepted

Solution code:
import sys, bisect

def solve():
    A = list(map(int, sys.stdin.readlines()))
    n = A[0]
    A = A[1:]
    L = A[:1]
    for a_i in A[1:]:
        if a_i > L[-1]:
            L.append(a_i)
        else:
            j = bisect.bisect_left(L, a_i)
            L[j] = a_i
    print(len(L))

solve()

Submission status: Accepted

Solution code:
from bisect import bisect
import sys
n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]
 #?????????i+1??§???????¢??????¨??????????????????????´????????°???????????´?
L = []
def LIS():
    L.append(A[0])
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L.append(A[i])
        else:
            if A[i] in L: continue
            j = bisect(L, A[i], 0, length) #L????????§?????????A[i]??\?????¨????????????????????????
            L[j] = A[i]
    return length + 1

print(LIS())

Submission status: Accepted

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:
            j = bisect_left(L, i)
            L[j] = i
    return len(L)

print(LIS())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import bisect
#D2
n = int(input())
a = [int(input()) for j in range(n)]
 
dp = [a[0]]
for i in range(1,n):
    if dp[-1] < a[i]:
        dp.append(a[i])
        #print(0,dp)
 
    else:
        dp[bisect.bisect_left(dp, a[i])] = a[i]
        #print(1,bisect.bisect_left(dp, a[i]),dp)
print(len(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = [int(input()) for j in range(n)]
dp = A[:1]
for a_i in A[1:]:
    if dp[-1] < a_i:
        dp.append(a_i)
    else:
        dp[bisect.bisect_left(dp, a_i)] = a_i
print(len(dp))

Submission status: Accepted

Solution code:
import sys
import bisect
n = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for j in range(n)]
dp = A[:1]
for a_i in A[1:]:
    if dp[-1] < a_i:
        dp.append(a_i)
    else:
        dp[bisect.bisect_left(dp, a_i)] = a_i
print(len(dp))

Submission status: Accepted

Solution code:
import bisect as bi
import sys
N = int(sys.stdin.readline())
C = [int(sys.stdin.readline()) for i in range(N)]
inf = 10000000000
lis = [inf for i in range(N)]
for c_i in C:
    lis[bi.bisect_left(lis, c_i)] = c_i
print(bi.bisect_left(lis, inf))

Submission status: Accepted

Solution code:
import bisect as bi
import sys
N = int(sys.stdin.readline())
C = [int(sys.stdin.readline()) for i in range(N)]
inf = 10000000000
lis = [inf] * N
for c_i in C:
    lis[bi.bisect_left(lis, c_i)] = c_i
print(bi.bisect_left(lis, inf))

Submission status: Accepted

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

N = int(readline())
a = [int(readline())]
append = a.append
for _ in [None]*(N-1):
    n = int(readline())
    if a[-1] < n:
        append(n)
    else:
        a[bisect.bisect_left(a, n)] = n

print(len(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
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_left(L, A[i])]  = A[i]
print(len(L))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


from bisect import bisect_left

def calc_LIS(A):
    dp = [float('inf')] * len(A)
    for a in A:
        i = bisect_left(dp, a)
        dp[i] = a
    return bisect_left(dp, float('inf'))


def main(args):
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = calc_LIS(A)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

readline = sys.stdin.readline
N = int(readline())
a = [int(readline()) for _ in [0]*N]
inf = float("inf")
dp = [inf]*N

for num in a:
    dp[bisect_left(dp, num)] = num

for i, num in zip(range(N, 0, -1), dp[::-1]):
    if num < inf:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

N = int(input())
inf = float("inf")
dp = [inf]*N

for n in map(int, sys.stdin.readlines()):
    dp[bisect_left(dp, n)] = n

for i, num in zip(range(N, 0, -1), dp[::-1]):
    if num < inf:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

N = int(input())
dp = [float("inf")]*N
result = -1

for n in map(int, sys.stdin.readlines()):
    i = bisect_left(dp, n)
    dp[i] = n
    result = i if i > result else result

print(result+1)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

N = int(input())
dp = []
append = dp.append
result = -1

for n in map(int, sys.stdin.readlines()):
    i = bisect_left(dp, n)
    if i > result:
        append(n)
        result += 1
    else:
        dp[i] = n

print(result+1)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = []
for i in range(n):
    num  = int(input())
    if A == []:
        A.append(num)
    elif num > A[-1]:
        A.append(num)
    else:
        j = bisect.bisect_left(A, num)
        A[j] = num
print(len(A))

Submission status: Accepted

Solution code:
# Longest Increasing Subsequence
import bisect

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


# def dfs(i, j):
#     if i == n:
#         return 0
#     if j < a[i]:
#         return 1 + dfs(i+1, a[i])
#     else:
#         return max(dfs(i+1, j), dfs(i+1, a[i]))
#
# print(dfs(i, -1))


L = [a[0]]
for x in a[1:]:
    if L[-1] < x:
        L.append(x)
    else:
        j = bisect.bisect_left(L, x)
        L[j] = x

print(len(L))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D&lang=jp
???????¨???????
???????¢??????¨??????
http://prdc.hatenablog.com/entry/2017/09/02/125842
'''
import bisect

n = int(input())
L = []

for i in range(n):
    a = int(input())
    z = bisect.bisect_left(L, a)
    if z >= len(L):
        L.append(a)
    else:
        L[z] = a

print(len(L))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))
N = int(input())
A = [int(input()) for _ in range(N)]

LIS = [A[0]]

for a in A[1:]:
    if a > LIS[-1]:
        LIS.append(a)
    else:
        LIS[bisect_left(LIS, a)] = a

print(len(LIS))

Submission status: Accepted

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

import bisect

if __name__ == '__main__':

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

    L = [None] * n
    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:
            indx = bisect.bisect_left(L[:length], a[i])
            L[indx] = a[i]

    print(length)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for i in range(N):
    index = bisect_left(LIS, A[i])
    if index >= len(LIS):
        LIS.append(A[i])
    else:
        LIS[index] = A[i]

print(len(LIS))

Submission status: Accepted

Solution code:
def nib(x):
    left = 0
    right = len(L[:length])
    mid = (left + right) // 2
    while 1:
        if mid == 0 or (L[mid] >= x and x > L[mid-1]):
            break
        if L[mid] > x:
            right = mid
        elif x > L[mid]:
            left = mid
        mid = (left + right) // 2
    return mid

N = int(input())
A = [int(input()) for _ in range(N)]
L = [0 for _ in range(N)]
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:
        L[nib(A[i])] = A[i]
print(length)

Submission status: Accepted

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

def lis_linear(a, n):
    dp = [0 for i in range(n)]
    longest = 1
    for i in range(n):
        max_val = 1
        for j in range(i):
            if a[j] < a[i] and max_val < dp[j] + 1:
                max_val = dp[j] + 1
        dp[i] = max_val
        if dp[i] > longest: longest = dp[i]
    return longest

def lis_binary(a, n):
    tail = [a[0]]
    for i in range(1, n):
        if a[i] > tail[-1]:
            tail.append(a[i])
            continue
        for j in range(len(tail)):
            if a[i] <= tail[j]:
                tail[j] = a[i]
                break
    return len(tail)

print(lis_binary(a, n))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
a = [int(input()) for i in range(n)]
dp = [0 for i in range(n)]
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:
        dp[bisect_left(dp[:length],a[i])] = a[i]
print(length)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

def solve():
    A = map(int, sys.stdin)
    n = next(A)
    L = [next(A)]
    for a_i in A:
        if a_i > L[-1]:
            L.append(a_i)
        else:
            j = bisect_left(L, a_i)
            L[j] = a_i
    print(len(L))

solve()

Submission status: Accepted

Solution code:
import bisect

def LIS():
    L.append(a[0])
    length[0] = 1
    
    for i in range(n-1):
        if L[-1]<a[i+1]:
            L.append(a[i+1])
            length[i+1] = length[i]+1
        else:
            L[bisect.bisect_left(L,a[i+1])] = a[i+1]
            length[i+1] = length[i]
            
    return length[-1]
    
n = int(input())
a = [int(input()) for _ in range(n)]

L = []
length = [None]*n

print(LIS())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18
arr = [INF]*(N+1)
arr[0] = -1
for a in A:
    l, r = 0, N
    while (r-l) > 1:
        mid = (r+l)//2
        if arr[mid] < a:
            l = mid
        else:
            r = mid
    arr[r] = a
for i in range(N, 0, -1):
    if arr[i] != INF:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

input = sys.stdin.readline


def binary_search(L, a, high):
    ng = -1
    ok = high
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if a <= L[mid]:
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    L = [0] * N
    L[0] = A[0]
    length = 1
    for a in A[1:]:
        if L[length - 1] < a:
            L[length] = a
            length += 1
        else:
            j = bisect_left(L, a, hi=length)
            L[j] = a

    print(length)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect

n = int(input())
dp = [float('inf')] * n

for _ in range(n):
    a = int(input())
    point = bisect.bisect_left(dp, a)
    dp[point] = a

print(bisect.bisect_left(dp, float('inf')))

Submission status: Accepted

Solution code:
INF = float('inf')
import bisect
L = list()
n = int(input())
for i in range(n):
  L.append(int(input()))
LIS = [INF] * n
for i in range(n):
  LIS[bisect.bisect_left(LIS, L[i])] = L[i]
for i in range(n):
  if(LIS[i] == INF):
    print(i)
    exit()
print(n)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    inf=float("inf")
    n=int(input())
    dp=[inf]*n
    for _ in range(n):
        a=int(input())
        dp[bisect_left(dp,a)]=a

    print(bisect_left(dp,10**10))

main()

Submission status: Accepted

Solution code:
INF = 10**9 + 7


def main():
    from bisect import bisect_left
    N = int(input())
    P = [int(input()) for i in range(N)]

    dp = [INF]*(N)
    for i in range(N):
        idx = bisect_left(dp, P[i])
        dp[idx] = P[i]
    print(bisect_left(dp, INF))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    LIS = [INF]*(N+1)
    for a in A:
        i = bisect_left(LIS,a)
        LIS[i] = a
    print(LIS.index(INF))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline
def LIS():
    N = int(input())
    INF = 10000000000
    dp = [INF] * (N+1)
    for _ in range(N):
        x = int(input())
        dp[bisect_left(dp, x)] = x
    print(bisect_left(dp, INF - 1))

LIS()

Submission status: Accepted

Solution code:
import bisect

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

cnt = []   
for a in A:
    i = bisect.bisect_left(cnt, a)
    if i >= len(cnt):
        cnt.append(a)
    elif cnt[i] > a:
        cnt[i] = a

print(len(cnt))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
a=[int(input()) for _ in range(n)]
dp=[float('inf') for _ in range(n)]
l=[]
l.append(a[0])
dp[0]=a[0]
for i in a[1:]:
    if l[-1]<i:
        l.append(i)
        dp[len(l)-1]=i
    else:
        x=bisect_left(l,i)
        dp[x]=i
        l[x]=i
print(len(l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
seq=[]
for i in range(n):
    seq.append(int(input()))

import bisect

Lis = [seq[0]]
for i in range(1,n):
    if seq[i] > Lis[-1]:
        Lis.append(seq[i])
    else:
        Lis[bisect.bisect_left(Lis,seq[i])] = seq[i]

print(len(Lis))

Submission status: Accepted

Solution code:
import bisect
INF=10**18
n=int(input())
a=[int(input()) for _ in range(n)]
dp=[]
for i in a:
  if bisect.bisect_left(dp,i)==len(dp):
    dp.append(i)
  else:
    dp[bisect.bisect_left(dp,i)]=i
print(len(dp))

Submission status: Accepted

Solution code:
import bisect

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

dp = []
for a in A:
  if len(dp)==0:
    dp.append(a)
  elif a > dp[-1]:
    dp.append(a)
  else:
    pos = bisect.bisect_left(dp, a)
    dp[pos] = a

print(len(dp))

Submission status: Accepted

Solution code:
# aのLongest Increasing Subsequence (LIS)を求めよ
# https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5
from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]  # a[i] >= 0

# dp[i] = min{a_ji | 長さがiのincreasing subsequence a_j0 < a_j1 < ... < a_ji}

dp = [a[0]]  # a[0] < dp[0]となる
for i in range(n):
    k = bisect_left(dp, a[i])
    if k == len(dp):
        dp.append(a[i])
    else:  # k < len(dp)
        dp[k] = a[i]

print(len(dp))

Submission status: Accepted

Solution code:
n = int(input())

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

dp = [0 for _ in range(n)]
dp[0] = A[0]
len = 1

def CeilIndex(A, l, r, key):
    while r-l > 1:
        m = (l+r) // 2
        if A[m] >= key:
            r = m
        else:
            l = m
    return r

for i in range(1, n):
    #print(A[i], dp)
    if A[i] < dp[0]:
        dp[0] = A[i]
    elif A[i] > dp[len-1]:
        dp[len] = A[i]
        len += 1
    else:
        dp[CeilIndex(dp, -1, len-1, A[i])] = A[i]
print(len)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = []
    for _ in range(n):
        tmp = ni()
        d.append(tmp)

    dp = [INF for _ in range(n + 1)]

    for di in d:
        idx = bisect.bisect_left(dp, di)
        dp[idx] = di

    for i in range(n, -1, -1):
        if dp[i] != INF:
            print(i + 1)
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    lis = [A[0]]
    for a in A[1:]:
        if a > lis[-1]:
            lis.append(a)
        else:
            idx = binary_search(lis, a)
            lis[idx] = a
    print(len(lis))


def binary_search(A, x):
    ok = len(A)
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if A[mid] >= x:
            ok = mid
        else:
            ng = mid
    return ok


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bisect(lst, isok, ok, ng):
    while(abs(ok-ng)>1):
        mid = (ok+ng)//2
        if isok(lst[mid]):
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for i in range(n)]
inf = 10**10
dp = [inf] * (n+1)
dp[0] = -1
for i in a:
    ind = bisect(dp, lambda x:x < i, -1, n+1) #dpは単調増加列なのでbisectが使える
    dp[ind+1] = min(dp[ind+1], i)

for i in range(n+1):
    if dp[n-i]!=inf:
        print(n-i)
        break

Submission status: Accepted

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

LIS = [nums[0]]

for num in nums:
    if LIS[-1] < num:
        LIS.append(num)
    else:
        LIS[bisect.bisect_left(LIS, num)] = num

print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

print(len(dp))