[백준 11722] 가장 긴 감소하는 부분 수열(Java)

1. 문제

www.acmicpc.net/problem/11722

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

2. 풀이

3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringTokenizer st;
	        st  = new StringTokenizer(br.readLine());
	        int n = Integer.parseInt(st.nextToken());
	        int []list = new int[n];
	        int []dp = new int[n+1];
	        st  = new StringTokenizer(br.readLine());

	        for(int i =0; i<n;i++){
	            list[i]= Integer.parseInt(st.nextToken());
	        }

	        dp[0]=1;
	        for(int i =1;i<n;i++){
	            dp[i]=1;
	            for(int j=0; j<i;j++){
	                if(list[j]>list[i] && dp[i]<=dp[j]){
	                    dp[i]=dp[j]+1;
	                }
	            }
	        }
	        int max =0;
	        for(int i : dp) max= Math.max(max,i);
	        System.out.println(max);
	}
}

반응형