r1 = lambda: sys.stdin.readline().strip()
T = int(r1())
for _ in range(T):
N = int(r1())
d=[]
ans = 0
a = r1().split(' ')
for i in range(N):
maxv = 0
for j in range(i):
if int(a[j]) < int(a[i]):
maxv = max(maxv, d[j])
d.append(maxv+1)
for i in range(N):
ans = max(ans, d[i])
print ans
safariworld
http://algospot.com/problems/read/LIS
Python으로 N이 500이길래 그냥 O(N^2)에 짰습니다. ( 물론 Test case는 미포함.) 그런데 TLE가 뜨네요 ㅠㅠ
다른데서 시간이 더 걸릴것 같지는 않은데... 살려주세요 ㅠㅠ
import sys
r1 = lambda: sys.stdin.readline().strip()
T = int(r1())
for _ in range(T):
N = int(r1())
d=[]
ans = 0
a = r1().split(' ')
for i in range(N):
maxv = 0
for j in range(i):
if int(a[j]) < int(a[i]):
maxv = max(maxv, d[j])
d.append(maxv+1)
for i in range(N):
ans = max(ans, d[i])
print ans
12년 전