LIS 문제 질문이요.

  • safariworld
    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년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    일단 a = map(int, r1().split()) 하시면 훨씬 빨라집니다만...
    그래도 느리긴 히네요. ^^; 2초로 제한시간 늘렸습니다.


    12년 전 link
  • safariworld
    safariworld

    으헉 감사합니다


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.