백준 11054

import java.util.Scanner;
 
public class Main{
    static public void main(String args[]){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
        //가장 긴 증가하는 수열 
        int arr []=new int [n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();
        int dp []= new int [n];
        int ans=1;
        for(int i=0;i<n;i++){
            int left=0; //왼쪽 최대길이
            int right=0; //오른쪽 최대길이 
            dp[i]=1;
            int dp1 []=new int [n]; //왼쪽용 dp
            int dp2 []=new int [n]; //오른쪽용 dp
            //왼쪽
            for(int a=0;a<i;a++){
                dp1[a]=1;
                for(int b=0;b<a;b++){
                	if(arr[a]<arr[i]) {
                		 if(arr[a]>arr[b])
                             dp1[a] = Math.max(dp1[a], dp1[b]+1);
                         left=Math.max(left,dp1[a]);
                	}
                    
                }
            }
            //오른쪽
            for(int a=i;a<n;a++){
                dp2[a]=1;
                for(int b=i;b<a;b++){
                	if(arr[a]<arr[i]) { //중심arr[i]보다 크면 안됨 
                		if(arr[a]<arr[b])
                            dp2[a] = Math.max(dp2[a], dp2[b]+1);
                        right=Math.max(right,dp2[a]);
                	}
                     
                }
            }
            dp[i]=dp[i]+right+left-1;
            ans=Math.max(dp[i],ans);
        }
         System.out.println(ans);
        
        
	}
     
 }

가장 긴 증가하는 부분 수열(왼쪽)+ 가장 긴 감소하는 부분 수열(오른쪽)-1

단, 중심이 되는 arr[i] 가 가장 크도록 체크하는 부분이 있어야 함