Boj 11054) 가장 긴 바이토닉 부분 수열

문제

백준 11054

설명

LIS 문제의 응용이다.

증가수열의 끝부분과 감소수열의 시작부분을 고정시키면 바이토닉 수열이 된다. 바이토닉 수열의 길이는 두 수열의 길이 -1 을 하면 구할 수 있다.

주어진 수 각각에 대해 위치를 고정하여 바이토닉 수열을 만들고, 그 중 최대 길이를 구하면 된다.

구하는 방법은 DP 를 사용하는게 더 빠르지만 이분탐색을 써도 제한시간 내에 풀린다.

시간 복잡도

O(\(\mathrm{N}^2\))

코드

int inputs[1001];
int dp1[1001], dp2[1001];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> inputs[i];

	for (int i = 0; i < n; i++)
	{
		dp1[i] = 1; dp2[n-i-1] = 1;
		for (int j = 0; j < i; j++)
		{
			if (inputs[j] < inputs[i])
				dp1[i] = max(dp1[i], dp1[j] + 1);
			if (inputs[n-j-1] < inputs[n-i-1])
				dp2[n-i-1] = max(dp2[n-i-1], dp2[n-j-1] + 1);
		}
	}

	int ans = -1;
	for (int i = 0; i < n; i++)
		ans = max(ans, dp1[i] + dp2[i]-1);
	cout << ans;
}