Longest Increasing Sequence (알고스팟) (LIS) [JAVA]

 

문제

문제 링크 : www.algospot.com/judge/problem/read/LIS

algospot.com :: LIS

문제 ID	시간 제한	메모리 제한	제출	정답	정답 비율
2초	2000ms	65536 KB	14154	4067	28%

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라. 어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

출력

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

 

풀이

subsequences배열에 LIS의 길이를 저장해놓는다.

subsequences[i] = i번째가 마지막인 순증가 최대길이라 할때

1부터 n까지 for문을 돌리는데, 이때 이전 숫자들을 매번 확인하면서 현재 길이가 최대가 될 수 있도록 한다.

 

코드

public class Main {
  public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    static int n, ans;
    static int[] numbers;
    static int[] subsequences;
    
    public static void main(String[] args)throws Exception {
    	int C = Integer.parseInt(br.readLine());
    	String[] s;
    	
    	for(int i =0; i<C; i++) {
    		n = Integer.parseInt(br.readLine()); 
    		ans = 0;
    		numbers = new int[n];
    		//시작하는 숫자별 순증가 길이
    		subsequences = new int [n];    		
    		s = br.readLine().split(" ");
    		for(int j =0; j<n; j++) {
    			numbers[j] = Integer.parseInt(s[j]);
    		}
    		findsub();
    		sb.append(ans).append("\n");
    	}
    	System.out.println(sb.toString());
    }    
    public static void findsub() {
    	for(int i=0; i<n; i++) {
    		subsequences[i] = 1;
    		for(int j=0; j<i; j++) {
    			//앞에 숫자보다 크고(추가 가능)
    			if(numbers[i] > numbers[j]) {
    				//앞에 숫자들이 가진 배열 중 가장 길게 유지
    				if(subsequences[j]+1 > subsequences[i]) {
    					subsequences[i] = subsequences[i]+1;
    				}
    			}
    		}
    		ans = Math.max(subsequences[i], ans);
    	}
    }
}

 

결과