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

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int ans = 0;
		int n = sc.nextInt();
		int arr[] = new int[n];
		int dp[] = new int[n];
		
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		
		for (int i = 0; i < n; i++) {
			int max = 0;
			for (int j = 0; j < i; j++) {
				if(arr[j] < arr[i]) {
					max = Math.max(max,dp[j]);
				}
			}
			dp[i] = max+1;
			ans = Math.max(ans,dp[i]);
		}
		System.out.println(ans);
	}
}

👨🏻‍💻 결과

 

 

🔗 링크

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

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