[백준] 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

dp 복습시간.. dp 왜어려워..

 

 

[풀이]

• 현재 탐색중인 값 기준으로 더 작은 값들 중 가장 큰 dp값 +1
• 예를 들어 탐색하는 값이 30이라면, 앞의 수 중 30보다 작은 수들의 dp값 중 max+1 
• 최종적으로 0~n-1의 dp 값 중 가장 큰 값 출력 

---

[소스코드]

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		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[0]=1;
		
		int max; 
		for(int i=1; i<n; i++) {
			max=0; 
			for(int j=0; j<i; j++) {
				if(arr[j] < arr[i]) max=Math.max(dp[j], max); 
			}
			dp[i]= max+1; 
		}
		max= 0; 
		for(int i=0; i<n; i++) {
			max =Math.max(max, dp[i]); 
		}
		System.out.println(max);
	}//end of main
}//end of class