LIS 질문입니다.

  • draner
    draner

    소스를 첨부하였습니다.

    시간초과라도 나면 알고리즘이 틀렸다고 생각합니다.

    하지만 시간 초과도나지 않고 오답이라고 뜹니다.

    제가 testcase를 넣어서 해봤는데 전부 정답입니다..

    어디가 틀렸을까요...

    답답한 마음뿐입니다..

    C++로 짯습니다. .

    using namespace std;

    int arr[501];
    int main(){
    int testcase;int inputNum;
    int answer=0,fanswer=0;

    cin>> testcase;
    for(int t=0; t<testcase; t++){
        cin>>inputNum;
        int min=0;
        answer=0;
        fanswer=0;
        for(int i=0; i<inputNum; i++){
            arr[i]=0;
            cin >> arr[i];
    
        }
    
        int start=0;
        for(int i =0; i<inputNum; i++){
            start= arr[i];
            for(int j=i+1; j<inputNum; j++){
                if(start<arr[j]){
    
                    answer++;
                    start= arr[j];
                }
                else if(start>arr[j])
                {
                    if(answer>fanswer){
                        fanswer =answer;
    
                    }
                    if(arr[j]> arr[i]){
                    start= arr[j];
                    answer =1;
                    }
                    else{
                    start= arr[j];
                    answer =0;
    
                    }
                }
            }
            if(answer>fanswer){
                fanswer =answer;
            }
    
            answer =0;
        }
    
        cout<<fanswer+1<<endl;
    
    
    }

    return 0;
    }


    3년 전
2개의 댓글이 있습니다.
  • lewha0
    lewha0

    일단 fanswer에 1을 더하여 출력하는게 이상한 것 같고요,
    1 9 2 8 3 7 4 6 5(9개)에 대해서 답이 맞게 나오는지 확인해 보시기 바랍니다.


    3년 전 link
  • draner
    draner

    감사합니다. 해당 경우를 생각하지 못하고 짰네요.... 다시 짜야겠습니다.


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