백준 11054번

원본 : www.acmicpc.net/problem/11054

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

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {

		int n = Integer.parseInt(reader.readLine());
		int arr[] = new int[n];
		int asc[] = new int[n];
		int desc[] = new int[n];
		int count = 0;
		
		String str = reader.readLine();
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(str.split(" ")[i]);
		}
		
		for (int i = 1; i < n; i++) {
			count = 0;
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j] && asc[j] >= count) {
					count++;
				}
			}
			asc[i] = count;
		}
		
		for (int i = arr.length - 2; i >= 0; i--) {
			count = 0;
			for (int j = arr.length - 1; j > i; j--) {
				if (arr[i] > arr[j] && desc[j] >= count) {
					count++;
				}
			}
			desc[i] = count;
		}
		
		int result[] = new int[n];
		for (int i = 0; i < n; i++) {
			result[i] = asc[i] + desc[i];
		}
		
		writer.write(maxValueInArray(result) + 1 + "");
		writer.flush();
	}
	
	public static int maxValueInArray(int arr[]) {
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		return max;
	}

}