LIS (최장 증가 부분수열) 문제..

  • jspac
    jspac

    http://www.algospot.com/problems/read/LIS

    그냥 잘 알려진 알고리즘대로 구현했는데요..
    예제로 주어진 수열들에 대해선 다 맞는 답을 내놓는데,
    submit을 하면 계속 WA가 뜨네요.. 제가 구현을 잘못 한건지...

    일단 소스는 아래와 같은데,
    어디가 잘못된 건가요?

    #include

    const int MAX_LEN = 500;

    int main(void)
    {
    int t, T, n, N, seq[MAX_LEN], k, len, max_len, len_lis[MAX_LEN];

    scanf("%d", &T);
for (t = 0; t < T; t++)
{
    scanf("%d", &N);

    if (N <= 0)
    {
        printf("0\n");
        continue;
    }

    for (n = 0; n < N; n++)
    {
        scanf("%d", seq + n);

        max_len = 1;
        for (k = 0; k < n; k++)
            if (seq[k] <= seq[n])
            {
                len = len_lis[k] + 1;
                if (len > max_len)
                    max_len = len;
            }
        len_lis[n] = max_len;
    }

    printf("%d\n", len_lis[N - 1]);
}

return 0;

    }


    13년 전
3개의 댓글이 있습니다.
  • wookayin
    wookayin

    N=4
    seq[0..N-1] = {3,3,3,3}

    이면 어떻게 되나요?


    13년 전 link
  • kcm1700
    kcm1700

    N=4
    seq[0..N-1] = {0,1,2,0}
    이면 잘 안 나올 것 같네요.

    len_lis[i]의 정의가 i번째 수를 포함하는 최장길이 증가수열인거죠? 문제에서 요구하는 답과 일치하는 걸 출력하게 하면 될 것 같아요.


    13년 전 link
  • jspac
    jspac

    윽, 그렇군요..ㅜㅜ
    kcm1700님, 감사합니다~


    13년 전 link

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