[DP] 가장 긴 바이토닉 부분 수열(백준 11054번, 자바)

 

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

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

 

 

 

[ 이분 탐색 활용하여 풀이 ]

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_11054_가장긴바이토닉부분수열 {
   
	 private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 static int answer=Integer.MIN_VALUE;
	 
   	public static void main(String[] args) throws NumberFormatException, IOException {
 
    	
    	int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        List<Integer> list = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        list.add(0);

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0 ; i < n; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
            
        }
        
        for(int i = 0 ; i < n; i++) {
        
        	//증가하는 부분 수열 구하기
            int value=arr[i];
            if(value > list.get(list.size() - 1)) list.add(value); //좌표 마지막 값보다 크면 뒤에 넣기 
            else{
                int left = 0;
                int right = list.size() - 1;

                while(left < right){
                    int mid = (left + right)/2;
                    if(list.get(mid) >= value){
                        right = mid;
                    }else{
                        left = mid + 1;
                    }
                }
               
                list.set(right, value);  //list 값을 갱신 
            }
            
            //감소하는 부분 수열
            list2.clear(); 
           list2.add(list.get(list.size()-1));
           
           //감소하는 부분 수열 구하기
           for(int j=i+1;j<n;j++) {
        	   
        	   	value=arr[j];
        	    
        	   if(value < list2.get(list2.size() - 1)) list2.add(value); //좌표 마지막 값보다 작으면
        	   else {
        	 	  	int left = 0;
        	 	  	int right = list2.size() - 1;

                    while(left < right){
                        int mid = (left + right)/2;
                        if(list2.get(mid) <= value){
                        	right=mid;
                        }else{
                        	left=mid+1;
                        }
                    }
                    if(left==0) continue;
      
                    //list 값을 갱신 
                    list2.set(right, value);
                }
           }
           
       
           answer=Math.max(answer, list.size()-2+list2.size());
           }
           
         
           System.out.println(answer);
            
        }
        
       
}