가장 긴 증가하는 부분 수열 4

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

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

 

// 코드

import java.util.*;
import java.io.*;
 
class Main{    
  
  public static void main(String[] args) throws Exception {
    // Please Enter Your Code Here
    StringBuilder sb  = new StringBuilder();
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
    int n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int myMax = Integer.MIN_VALUE;
    int[] arr = new int[n + 1];
    int[] dp  = new int[n + 1]; 
    
    // dp 초기화
    for(int i=1; i<=n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
      for(int j=0; j<i; ++j) {
        
        if( arr[i] <= arr[j] ) continue;
        dp[i] = Math.max(dp[j] + 1, dp[i]);
        myMax = Math.max(dp[i], myMax);
        
      }
    }
    
    sb.append(myMax + "\n");
    
    int value = myMax; 
    Stack<Integer> stack = new Stack<>();
    for(int i=n; i>=1; --i) {
      if(value != dp[i]) continue;
      // 현재 찾는 길이와 같은 경우, stack에 실제 값을 push한다.
      stack.push(arr[i]);
      value--;
    }
    
    while(!stack.isEmpty()) sb.append(stack.pop() + " ");
    sb.append("\n");
    
    bw.write(sb.toString()); 
    br.close();
    bw.flush();
    bw.close();
  }
}