가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

 

// 코드

import java.util.*;import java.io.*;
class Main{ 
  
  static int N;
  static int[] arr;
  static int[] lis_dp;
  static int[] lds_dp;
  
  public static void main(String[] args) throws Exception{
    
    // Please Enter Your Code Here
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    N =Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    arr    = new int[N]; 
    // LIS dp
    lis_dp = new int[N];    
    // LDS dp
    lds_dp = new int[N];
    
    for(int i=0; i<N; ++i) arr[i] = Integer.parseInt(st.nextToken());
    
    LIS();
    LDS();
    
    int max = 0;
    for(int i = 0; i < N; ++i) max = Math.max(max, lis_dp[i] + lds_dp[i]);
    
    bw.write(String.valueOf(max - 1));
    
    bw.flush();
    bw.close();
    br.close();
  }
  
  static void LIS() {
    for(int i = 0; i < N; ++i) {
      lis_dp[i] = 1;
      for(int j = 0; j < i; ++j) 
        if(arr[i] > arr[j] && lis_dp[i] < lis_dp[j] + 1) 
          lis_dp[i] = lis_dp[j] + 1;
    }
  }
  
  static void LDS() {
    for(int i = N - 1; i > -1; --i) {
      lds_dp[i] = 1;
      for(int j = N - 1; j > i; --j) 
        if(arr[j] < arr[i] && lds_dp[i] < lds_dp[j] + 1) 
          lds_dp[i] = lds_dp[j] + 1;
    }
  }
  
}