[ 자바 /Java ] 백준 11722 : 가장 긴 감소하는 부분 수열

문제

---

 

 

---

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class LDS_11722 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] A = new int[n];
		int[] dp = new int[n];
		int result = 0;
		
		st = new StringTokenizer(br.readLine());

		for( int i=0; i<n; i++ ) {
			A[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
			
			for( int j=i-1; j>=0; j-- ) {	// j = 5~0
				if( A[j] > A[i] && dp[i] <= dp[j] ) {
					dp[i] = dp[j] +1;
				}
			}
			result = Math.max( result, dp[i] );
		}
		System.out.println( result );
	}
}