2개의 댓글이 있습니다.
-
-
safariworld -
으헉 감사합니다
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
으헉 감사합니다
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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년 전