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: Wrong Answer

Solution code:
import bisect
a = int(input())
b = [int(input()) for 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: Wrong Answer

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)]
    dp[0] = 0
    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) - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

arr = []

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


dp = [0 for i in range(n)]

for i in range(n):
	dp[i] = 1
	for j in range(i):
		if arr[i] > arr[j]:
			dp[i] = max(dp[i], dp[j] + 1)

print dp[n-1]

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

@lru_cache(None)
def dp(n, a):
    if n == N:
        return 0
    if s[n] <= a:
        return 0
    return max(dp(n + 1, a), dp(n + 1, s[n]) + 1)

N = int(input())
s = [int(input()) + 1 for i in range(N)]
print(dp(0, 0))

Submission status: Wrong Answer

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

dp = [1] * n
for i in range(n):
    ans = 0
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)

    ans = max(ans,dp[i])

print(ans)

Submission status: Wrong Answer

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

dp = [1] * n
for i in range(n):
    ans = 0
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)

    ans = max(ans,dp[i])

print(ans)

Submission status: Wrong Answer

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'):
        print(i)
        break

Submission status: Wrong Answer

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]
print dp
for i in xrange(n):
    if dp[i]==float('inf'):
        i-=1
        break
print(i+1)

Submission status: Wrong Answer

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

lis = [numbers[0]]
for last in numbers[1:]:
    for i, item in enumerate(lis):
        if last < item:
            lis = lis[:i] + [last] + lis[i+1:]
            break
    if lis[-1] < last:
        lis.append(last)

print(len(lis))

Submission status: Wrong Answer

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

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

for i, ai in enumerate(array):
    dp[i] = max((dp[j] for j, aj in enumerate(dp[:i]) if aj < ai), default=0) + 1

print(max(dp))

Submission status: Wrong Answer

Solution code:
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[-1] = targ[n]
print(len(ans))

Submission status: Wrong Answer

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>=a[index]:
        return 0

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

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

for i in range(n):
    a[i]=int(input())
dp=[[-1 for i in range(max(a)+1)] for j in range(n+1)]

print(dfs(0,0,n,a,dp))

Submission status: Wrong Answer

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>=a[index]:
        return 1

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

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

for i in range(n):
    a[i]=int(input())
dp=[[-1 for i in range(max(a)+1)] for j in range(n+1)]

print(dfs(0,0,n,a,dp))

Submission status: Wrong Answer

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

for i in range(n):
    a[i]=int(input())
max_a=max(a)+1
dp=[[-1 for i in range(max_a)] for j in range(n+1)]

for i in range(max_a):
    dp[n][i]=0

i=n-1
while i>=0:
    for j in range(max_a):
        if j>=a[i]:
            dp[i][j]=0
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][a[i]]+1)
    i-=1
print(dp[0][0])

Submission status: Wrong Answer

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 0

    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())
max_a=max(a)+1
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: Wrong Answer

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 0

    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: Wrong Answer

Solution code:
# Time Complexity: O(n^2)
# TLE
n, A = int(raw_input()), []
for i in xrange(n):
    A.append(int(raw_input()))

res, cnt = [], 0
for i in xrange(len(A)):
    res.append(A[i])
    cur_cnt = 1
    for j in xrange(i+1, len(A)):
        if res[-1] < A[j]:
            res.append(A[j])
            cur_cnt += 1
            #print res
    cnt = max(cur_cnt, cnt)
    res = []

print cnt

Submission status: Wrong Answer

Solution code:
# Time Complexity: O(n^2)
# TLE
n, N = int(raw_input()), []
for i in xrange(n):
    N.append(int(raw_input()))

def LIS(lis, A, flag):
    if flag == 1 and len(A) != 0:
        lis.append(A[0])

    if len(A) == 0:
        if len(lis) == 0: return 0
        return len(lis)
    elif len(lis) > 1:
        if lis[-2] > lis[-1]:
            return 0

    return max(LIS(lis[:], A[1:], 1), LIS(lis[:], A[1:], 0))

print max(LIS([], N[:], 1), LIS([], N[:], 0))

Submission status: Wrong Answer

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

def linear_lower_bound(arr, n, target):
    p = -1
    for i in xrange(n):
        if arr[i] <= target:
            p = i
    print p
    return p+1

def LIS(arr):
    L = [0] * len(arr)
    L[0] = arr[0]
    length = 1

    for i in xrange(1, len(arr)):
        #if len(L) == 0: L.append(i)
        if arr[i] > L[length - 1]:
            L[length] = arr[i]#L.append(A[i])
            length += 1
        else:
            L[linear_lower_bound(L, length, arr[i])] = arr[i]
    return len(L), L

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def linear_lower_bound(arr, n, target):
    p = -1
    for i in xrange(n):
        if arr[i] <= target:
            p = i
    return p+1

def linear_upper_bound(arr, n, target):
    p = -1
    for i in xrange(n):
        if arr[i] >= target:
            p = i
    return p+1


def LIS(arr):
    L = [0] * len(arr)
    L[0] = arr[0]
    length = 1

    for i in xrange(1, len(arr)):
        #if len(L) == 0: L.append(i)
        if arr[i] > L[length - 1]:
            L[length] = arr[i]#L.append(A[i])
            length += 1
        else:
            L[linear_lower_bound(L, length, arr[i])] = arr[i]
    return length

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

global L, arr, n
def _input(n):
    #return [int(raw_input()) for i in xrange(n)]
    for i in xrange(n):
        arr[i] = int(raw_input())

def _lower_bound(arr, n, target):
    '''
    :return: a value not less than target, value >= target
    '''
    l, r = 0, n - 1 # r is index at 1
    pos = 0
    while l < r:
        pos = (l + r) / 2
        if arr[pos] > target:
            r = pos
        else: # <=
            l = pos + 1

    return r#(l + r) / 2 # Need to fix

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

L = [0] * 100000
arr = [0] * 100001
def LIS():
    global L, arr, 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:
            L[lower_bound(L[:length], arr[i])] = arr[i]
    return length, L

#==============================================
def main():
    global L, arr, n

    n = int(raw_input())
    _input(n)
    LIS()
    print len(set(L))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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] != arr[i]: # Fix common item - Dont insert common item
                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]

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = int(input())
A = []
for i in range(n):
 A.append(int(input()))
 
 L = [None for i in range(n)]
def LIS():
    L[0] = A[0]
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L[length] = A[i]
        else:
            j = bisect(L, A[i], 0, length)
            L[j] = A[i]
    return length + 1

print(LIS())

Submission status: Wrong Answer

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

gra = [1]*n
Max = 1

for i in range(1,n):
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

Submission status: Wrong Answer

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

gra = [1]*n
Max = 1

for i in range(1,n):
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
    gra[i] = Max+1

print(max(gra))

Submission status: Wrong Answer

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

gra = [1]*n

for i in range(1,n):
    Max = 1
    for j in range(Max,i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

Submission status: Wrong Answer

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

gra = [1]*n
Max = 1
for i in range(1,n):

    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(Max+1)

Submission status: Wrong Answer

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

gra = [1]*n
Max = 1
for i in range(1,n):

    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1
            Max += 1
print(Max)

Submission status: Wrong Answer

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])
    elif L[-1] > A[i]:
        L[bisect(L, A[i])]  = A[i]
print(len(L))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = max(dp)
    for j in range(i):
        if dpmax == dp[j]:
            if num > A[j]:
                dp[i] = dp[j] + 1
                break
    else:
        dp[i] = dpmax
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(1, n):
    num = int(input())
    A.append(num)
    dpmax = max(dp)
    for j in range(i):
        if max == dp[j]:
            if num > A[j]:
                dp[i] = dp[i-1] + 1
                break
    else:
        dp[i] = dpmax
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(1, n):
    num = int(input())
    A.append(num)
    dpmax = max(dp)
    for j in range(i):
        if dpmax == dp[j]:
            if num > A[j]:
                dp[i] = dp[i-1] + 1
                break
    else:
        dp[i] = dpmax
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = max(dp)
    for j in range(i):
        if dpmax == dp[j]:
            if num > A[j]:
                dp[i] = dp[i-1] + 1
                break
    else:
        dp[i] = dpmax
        
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = 1
    for j in range(i):
        if A[j] < num and dp[j] > dpmax:
            dpmax = dp[j]
    dp[i] = dpmax + 1    
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = 0
    for j in range(i):
        if A[j] < num and dp[j] > dpmax:
            dpmax = dp[j]
    dp[i] = dpmax + 1    
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = 0
    for j in range(i):
        if A[j] < num and dp[j] > dpmax:
            dpmax = dp[j]
    dp[i] = max(dpmax + 1,1)    
print(dp[-1])

Submission status: Wrong Answer

Solution code:
# fp = open("DPL_1_D-in11.txt")
# inlist = list(map(int, fp.read().splitlines()))
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = 0
    for j in range(i):
        if A[j] < num and dp[j] > dpmax:
            dpmax = dp[j]
    dp[i] = max(dpmax + 1, 1)    
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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])
    dp.append(a[i])
    if(length < k):
        dp.append(a[i])
        length += 1
    else:   #挿入位置が長さよりも小さい時
        dp[k] = a[i]
print(length+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append( int(input()) )
#dp[i]:a[i]が最後になる数列の最大長

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

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i],dp[j]+1 )
        else:
            dp[i] = 1
        #print(i,j,dp[i])
print(max(dp))

Submission status: Wrong Answer

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)]
    for i in range(n):
        max_val = 1
        for j in range(i):
            if max_val < dp[j]: max_val = dp[j]
            if a[j] < a[i] and max_val < dp[j] + 1: max_val = dp[j] + 1
        dp[i] = max_val
    return dp[-1]

print(lis_linear(a, n))

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
dp = [0 for i in range(n)]
dp[0] = 1
for i in range(1, n):
    dp[i] = dp[i - 1]
    if a[i] > a[i-1]: dp[i] += 1
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
parent = [[i, 1] for i in range(n)]
def root(x):
	if parent[x][0] == x:
		return x
	parent[x][0] = y = root(parent[x][0])
	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[y] = [px, parent[x][1]+1]
	return

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

Submission status: Wrong Answer

Solution code:
n = int(input())
parent = [[i, 1] for i in range(n)]
def root(x):
	if parent[x][0] == x:
		return x
	parent[x][0] = y = root(parent[x][0])
	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[y] = [px, parent[x][1]+1]
	return

Q = []
for i in range(n):
	a = int(input())
	for j in range(i):
		if Q[-j-1] >= a:
			continue
		union(i-j-1, i)
		break
	Q += [a]
print(max(map(lambda x: x[1], parent)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

arr = []

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


dp = [0 for i in range(n)]

for i in range(n):
	dp[i] = 1
	for j in range(i):
		if arr[i] > arr[j]:
			dp[i] = max(dp[i], dp[j] + 1)

print max(dp)

Submission status: Time Limit Exceeded

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

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

dp = [-float('inf')]

for ai in a:
    for i in range(1, len(dp)):
        if dp[i - 1] < ai and ai < dp[i]:
            dp[i] = ai
    if dp[-1] < ai:
        dp.append(ai)

print(len(dp) - 1)

Submission status: Time Limit Exceeded

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

dp = [1] * n
ans = 0
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)

    ans = max(ans, dp[i])

print(ans)

Submission status: Time Limit Exceeded

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

lis = [-float("inf"),numbers[0]]
for last in numbers[1:]:
    for i, (left, right) in enumerate(zip(lis, lis[1:])):
        if left < last and last < right:
            lis = lis[:i+1] + [last] + lis[i+2:]
            break
    if lis[-1] < last:
        lis.append(last)

print(len(lis)-1)

Submission status: Time Limit Exceeded

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:]:
    pos = bisect.bisect_left(lis, last)
    if len(lis) < pos:
        lis.append(last)
    else:
        lis = lis[:pos] + [last] + lis[pos+1:]

print(len(lis))

Submission status: Time Limit Exceeded

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

for i, ai in enumerate(array):
    dp[i] = max((dp[j] for j, aj in enumerate(array[:i]) if aj < ai), default=0) + 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    ans = max(dp)

    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: Time Limit Exceeded

Solution code:
# Time Complexity: O(n^2)
# TLE
n, N = int(raw_input()), []
for i in xrange(n):
    N.append(int(raw_input()))

def LIS(lis, A, flag):
    '''
    '''
    if flag == 1 and len(A) != 0:
        lis.append(A[0])

    if len(A) == 0:
        if len(lis) == 0: return 0
        return len(lis)
    elif len(lis) > 1:
        if lis[-2] >= lis[-1]:
            return 0

    return max(LIS(lis[:], A[1:], 1), LIS(lis[:], A[1:], 0))

print max(LIS([], N[:], 1), LIS([], N[:], 0))

Submission status: Time Limit Exceeded

Solution code:
def _input(n):
    return [int(raw_input()) for 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: Time Limit Exceeded

Solution code:
# Lingest Increasing Subsequence
# Given input: the length of the sequence followed by the sequence
def LIS():
    length = int(input())
    sequence = []
    for i in range(length):
        sequence.append(int(input()))
    
    L = []
    for i in range(length):
        temp = [0]
        for j in range(0, i):
            if sequence[j] < sequence[i]:
                temp.append(L[j])
        L.append(1 + max(temp))
    return max(L)

if __name__ == '__main__':
     print(LIS())

Submission status: Time Limit Exceeded

Solution code:
import heapq as h

# Lingest Increasing Subsequence
# Given input: the length of the sequence followed by the sequence
def LIS():
    length = int(input())
    sequence = []
    for i in range(length):
        sequence.append(int(input()))
    
    L = []
    for i in range(length):
        temp = [0]
        for j in range(0, i):
            if sequence[j] < sequence[i]:
                h.heappush(temp, -L[j])
        L.append(1 - temp[0])
    return max(L)

if __name__ == '__main__':
     print(LIS())

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    A = list(map(int, sys.stdin.readlines()))
    n = A[0]
    A[0] = -1
    L = [0] * (n + 1)
    for i, a_i in enumerate(A[1:], start=1):
        k = 0
        for j, a_j in enumerate(A[:i]):
            if a_j < a_i and L[j] > L[k]:
                k = j
        L[i] = L[k] + 1
    print(max(L))

solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
n = int(input())
A = []
for i in range(n):
 A.append(int(input()))
 
 L = [None for i in range(n)]
def LIS():
    L[0] = A[0]
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L[length] = A[i]
        else:
            if A[i] in L: continue
            j = bisect(L, A[i], 0, length)
            L[j] = A[i]
    return length + 1

print(LIS())

Submission status: Time Limit Exceeded

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

gra = [1]*n


for i in range(1,n):
    Max = 1
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

Submission status: Time Limit Exceeded

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

gra = [1]*n

for i in range(1,n):
    Max = 1
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

Submission status: Time Limit Exceeded

Solution code:
# fp = open("DPL_1_D-in11.txt")
# inlist = list(map(int, fp.read().splitlines()))
n = int(input())
A = []
dp = [0 for _  in range(n)]
dp[0] = 1
for i in range(n):
    num = int(input())
    A.append(num)
    dpmax = 0
    for j in range(i):
        if A[j] < num and dp[j] > dpmax:
            dpmax = dp[j]
    dp[i] = max(dpmax + 1, 1)    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append( int(input()) )
#dp[i]:a[i]が最後になる数列の最大長

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

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i],dp[j]+1 )
        else:
            dp[i] = max(1,dp[i])
        #print(i,j,dp[i])
print(max(dp))

Submission status: Time Limit Exceeded

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

print(lis_linear(a, n))

Submission status: Time Limit Exceeded

Solution code:
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:
        for j in range(length):
            if dp[j] >= a[i]:
                dp[j] = a[i]
                break
print(length)

Submission status: Memory Limit Exceeded

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>=a[index]:
        return 0

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

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

for i in range(n):
    a[i]=int(input())
dp=[[-1 for i in range(max(a)+1)] for j in range(n+1)]

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

Submission status: Memory Limit Exceeded

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

for i in range(n):
    a[i]=int(input())
max_a=max(a)+1
dp=[[-1 for i in range(max_a)] for j in range(n+1)]

for i in range(max_a):
    dp[n][i]=0

i=n-1
while i>=0:
    for j in range(max_a):
        if j>=a[i]:
            dp[i][j]=0
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][a[i]]+1)
    i-=1
if dp[0][0]==0:
    print(1)
else:
    print(dp[0][0])

Submission status: Memory Limit Exceeded

Solution code:
n=int(input())
a=[0 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)]

for i in range(n+1):
    dp[n][i]=0

i=n-1
while i>=0:
    for j in range(n+1):
        if j!=0 and a[j-1]>=a[i]:
            dp[i][j-1]=dp[i+1][j-1]
        else:
            dp[i][j-1]=max(dp[i+1][j-1],dp[i+1][i]+1)
    i-=1

sum=dp[0][n]

if sum==0:
    print(1)
else:
    print(sum)

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:
import bisect
a = int(input())
b = [int(input()) for d in range(a)]
c = [b[0]]
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: Accepted

Solution code:
import bisect

INF = 1 << 30


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

Solution code:
import bisect
n = int(input())
inf = float("inf")
arr = [int(input()) for _ in xrange(n)]

dp = [inf for _ in xrange(n)]

for i in arr:
	ind = bisect.bisect_left(dp,i)
	dp[ind] = i

print bisect.bisect_left(dp,inf)

Submission status: Accepted

Solution code:
import sys
import bisect

def lis(arr):
    queue = []
    queue.append(arr[0])
    for num in arr[1:]:
        if num > queue[-1]:
            queue.append(num)
        else:
            idx = bisect.bisect_left(queue, num)
            queue[idx] = num
    return len(queue)
    
    
if __name__ == '__main__':
    N = sys.stdin.readline()
    N = int(N)
    arr = []
    for i in range(N):
        tmp = sys.stdin.readline()
        arr.append(int(tmp))
    
    sys.stdout.write(str(lis(arr)))
    sys.stdout.write('\n')

Submission status: Accepted

Solution code:
from sys import stdin
from bisect import bisect_left, bisect_right
readline = stdin.readline

dp = [-float('inf')]

for ai in (int(readline()) for _ in range(int(readline()))):
    if dp[-1] < ai:dp.append(ai)
    for i in range(bisect_right(dp, ai), bisect_left(dp, ai) + 1):dp[i] = ai
print(len(dp) - 1)