0%

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

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11053

Review

  • 나무위키 최장 증가 부분 수열를 참고해서 풀었다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 1;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = 1;
      for(int j = 1; j <= i; j++) {
        if(A[i] > A[j]) {
          DP[i] = Math.max(DP[i], DP[j] + 1);
        }
      }
      ans = Math.max(ans, DP[i]);
    }
    
    System.out.println(ans);
    
  }
  
}