[BOJ] 11722: 가장 긴 감소하는 부분 수열 (JAVA)

11722번: 가장 긴 감소하는 부분 수열

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버2_117722_가장긴감소하는부분수열 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		int arr[] = new int[N];
		int dp[] = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
 		}

		int num = 1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<i; j++) {
				if(arr[i] < arr[j] && dp[i] < dp[j]+1) {
					dp[i] = dp[j]+1;
					num = Math.max(num, dp[i]);
				}
			}
		}
		
		sb.append(num);
		bw.write(sb.toString());
		bw.close();
	}
}