11053 가장 긴 증가하는 부분 수열 (JAVA)

• "dy[i] : i번째 수로 만들 수 있는 가장 긴 증가 수열" 원리를 사용하는 동적 계획법 기초 문제

• 주의할 점은 수열의 갯수가 하나가 들어오면, 1을 출력하도록 처리해야 한다. 이유는 LIS 알고리즘이 수열의 두번째 인자부터 시작하기 때문

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int answer = 0;
        int[] arr = new int[n];
        int[] dy = new int[n];
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();

        dy[0] = 1;	// 한 숫자로 무조건 하나의 수열은 만들 수 있다.
        for(int i=1; i<arr.length; ++i){
            int max = 0;
            for(int j=i-1; j>=0; j--){
                if(arr[i] > arr[j] && dy[j] > max)
                    max = dy[j];
            }
            dy[i] = max + 1;
            answer = Math.max(dy[i], answer);
        }
        if(n==1)
            System.out.println(1);	// n이 1일 경우 0이 출력됨을 방지
        else
            System.out.println(answer);
    }
}