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

문제출처 : https://www.acmicpc.net/problem/11054

1. 문제요약

- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... Sn-1 > Sn 을 만족한다면, 그 수열을 바이토닉 수열

- A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}

  A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 가장 긴 바이토닉 수열의 길이는 7

2. 접근방법

- 좌측 LIS / 우측 LIS

3. 시간복잡도

- 2n^2 + n

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, dl[1001], dr[1001], a[1001], ans;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		dl[i] = 1;
		dr[i] = 1;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			if (a[i] > a[j] && dl[i] < dl[j] + 1)
				dl[i] = dl[j] + 1;
	for (int i = n - 1; i >= 0; i--)
		for (int j = n - 1; j > i; j--)
			if (a[i] > a[j] && dr[i] < dr[j] + 1)
				dr[i] = dr[j] + 1;
	for (int i = 0; i < n; i++)
		if (ans < dl[i] + dr[i]) ans = dl[i] + dr[i];
	cout << ans - 1 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]