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

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

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 구하면 가장 긴 바이토닉 부분 수열을 구할 수 있다.

LIS 의 길이가 5 이고 LDS 의 길이가 3 인 경우 바이토닉 부분 수열의 길이가 가장 길다.

LIS = [1, 2, 3, 4, 5] LDS = [5, 2, 1] 이 때 LIS 의 끝 값과 LDS 의 시작 값을 두 번 더하기 때문에 길이는 1을 빼 주면 된다.

LDS 를 구하는 방법으로는 구하고자 하는 수열을 뒤집어 증가하는 부분 수열의 길이 배열을 구한 뒤 다시 뒤집는 방법도 있다.

그게 훨씬 간단하긴 한데.. 아직 LDS 를 구할 때 뒤에서 부터 LIS 를 구하는 것처럼 하는게 더 편하다..

---

import sys


def up(data):
	dp = [1 for _ in range(n)]

	for i in range(n):
		for j in range(i):
			if data[i] > data[j]:
				dp[i] = max(dp[i], dp[j] + 1)

	return dp


def down(data):
	dp = [1 for _ in range(n)]

	for i in range(n, -1, -1):
		for j in range(i, n):
			if data[i] > data[j]:
				dp[i] = max(dp[i], dp[j] + 1)

	return dp


def solution():
	up_dp = up(arr)
	down_dp = list(reversed(up(arr[::-1])))

	answer = [i + j - 1 for i, j in zip(up_dp, down_dp)]
	return max(answer)


if __name__ == "__main__":
	n = int(input())
	arr = list(map(int, sys.stdin.readline().rsplit()))

	print(solution())