LIS 문제 제 힘으로는 힘들어서 질문드립니다.

  • rlftpgus
    rlftpgus

    3중 for문 이용해서 전체 탐색 알고리즘으로 짜봤습니다.
    많은 답안 집어넣어봐도 못풀겠어서 질문드립니다.
    잘못된점이나 입력 예시 하나정도만 주시면 감사하겠습니다.
    https://algospot.com/judge/problem/read/LIS

    #include <stdio.h>
    int solve(int l[500],int n)
    {
        int i,j,k;
        int max,now,mn,f;
        max=0;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                mn=1;
                f=0;
                now=i;
                for(k=j;k<n;k++)
                {
                    if(l[now]<l[k])
                    {
                        mn++;
                        now=k;
                    }
                    else if(f==0&&l[i]<l[k])
                    {
                        j=k-1;
                        f=1;
                    }
                }
                if(mn>max)
                {
                    max=mn;
                }
                if(f==0)
                    break;
            }
        }
        return max;
    }
    int main(void) {
        int c,n,l[500],max;
        int i;
        scanf("%d",&c);
        while(c--)
        {
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d",&l[i]);
    
            }
            max=solve(l,n);
            printf("%d",max);
            if(c>0)
                printf("\n");
        }
            return 0;
    }
    

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