백준 동적계획법 - 11054번 : 가장 긴 바이토닉 부분 수열

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

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

---

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] num = new int[n+1];
		int[] memo = new int[n+1];
		int[] memo2 = new int[n+1];
		for(int i=1; i<=n; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		int max = -1;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<i; j++) {
				if(num[j]<num[i]) {
					memo[i] = Math.max(memo[j]+1,memo[i]);
				}
			}
			if(memo[i]==0) memo[i] = memo[0]+1;
			
		}
		for(int i=n; i>=1; i--) {
			for(int j=n; j>i; j--) {
				if(num[j]<num[i]) {
					memo2[i] = Math.max(memo2[j]+1, memo2[i]);
				}
			}
			if(memo2[i]==0) memo2[i] = memo[0]+1; 
		}
		for(int i=1; i<=n; i++) {
			if(max<memo[i]+memo2[i]) {
				max = memo[i]+memo2[i];
			}
		}
		
		bw.write(max-1+"");
		bw.close();
	}
	
}