LIS(최대 부분 증가 수열) 문제 오답이자꾸뜹니다.

  • pchanwan
    pchanwan

    package _8;

    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Scanner;
    import java.util.Vector;

    public class LIS {
    public static int length = 0;
    public static int max = 1;
    public static int [] cache;
    public static int [] sequence;
    public static void main(String [] args) {
    Scanner scanner = new Scanner(System.in);
    int testcaseNum = scanner.nextInt();
    for(int i = 0; i < testcaseNum; i ++) {
    length = scanner.nextInt();
    cache = new int[501];
    sequence = new int[501];
    Arrays.fill(cache, -1);
    for(int j = 0; j < length; j ++)
    sequence[j] = scanner.nextInt();

    recusive(0, cache, sequence);
            System.out.println(max);
            //for(int ii = 0; ii < length; ii ++)
                //System.out.println(cache[ii]);
        }
    }
    public static void recusive(int start, int [] cache, int [] sequence) {
        cache[length-1] = 1;
    
        for(int i = length - 2; i >= 0; i --) {
            int index = 0;
            int count = 0;
            int first = 0;
            for(int j = i + 1; j < length; j ++) {
                if(sequence[i] < sequence[j]) {
                    count ++;
                    if(cache[j] == -1) {
                        recusive(j, cache, sequence);
                    }
                    else {
                        if(first == 0) {
                            index = j;
                            first ++;
                        }
                        else {
                            int temp = 0;
                            if(cache[index] < cache[j]) {
                                temp = index;
                                index = j;
                            }
                            if(cache[temp] == cache[j] && sequence[temp] < sequence[j]) {
                                index = j;
                            }
                        }
                    }
                }
            }
            if(count == 0) {
                cache[i] = 1;
                continue;
            }
            cache[i] = cache[index] + 1;
            max = max > cache[i] ? max : cache[i];
            //index = i - 1;
        }
    }

    }

    다ㅏ이나믹프로그래밍을 앞에서말고 뒤에서부터 진행했는데요 문제가뭘까요? 예외테스트케이스가 존재하는거같긴한데 찾기힘드네요 ㅠㅠ...도와주세요


    6년 전
1개의 댓글이 있습니다.
  • rumble99
    rumble99

    이미 해결하셨을 거라 생각되지만, 답변을 한 번 올려봅니다. 복수개의 정답을 "max"라는 Integer형 변수를 통하여 출력을 하시고 있습니다. 이렇게 되면 첫 번째 케이스 부터 끝날 때까지 정답 값이 오름차순으로 나온다면 문제가 없겠지만, 내림 차순으로 정답이 도출된다면 첫 번째 케이스에서 나온 값으로 제출을 하는 현상이 발생합니다. 즉, "max"값을 새로운 테스트 케이스 시작 할때 마다 초기화를 해주셔야 합니다.


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