[백준] 11722 : 가장 긴 감소하는 부분 수열 JAVA 풀이

 

import java.io.*;
import java.util.StringTokenizer;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수열의 길이를 입력받음
        int N = Integer.parseInt(br.readLine());
        // 수열을 저장할 배열 선언
        int[] arr = new int[N+1];
        // 감소 수열의 길이를 저장할 배열
        int[] dp = new int[N+1];

		// 초기화
        dp[1] = 1;
        // 수열의 값을 입력받기 위한 스트링토크나이저
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 수열의 값을 배열의 저장
        for(int i=1;i<=N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 수열의 값 하나씩 잡은 뒤
        // 이전에 나온 수들 중 자기보다 큰 수가 있으면
        // 그 수에서 현재 값으로 이동할 때가
        // 새로운 최대 길이인지 확인하고 업데이트
        for(int i=2;i<=N;i++) {
        	dp[i] = 1;
        	for(int j=0;j<i;j++) {
        		if(arr[i]<arr[j]&&dp[i]<=dp[j]+1) {
        			dp[i] = dp[j]+1;
        		}
        	}
        }
        
        // 최대 길이를 찾아서 출력
        int max = 0;
        for(int i : dp) max =Math.max(max, i);
        System.out.println(max);
    }
}