[C++] 백준 11054번 가장 긴 바이토닉 부분 수열

다이나믹 프로그래밍 문제입니다.

증가하는 수열의 값을 체크해서 DP에 넣고
감소하는 수열의 값을 체크해서 DP에 추가로 넣어서 문제를 풀었습니다.

증가하는 수열은 다음처럼 구했습니다.
for (int i = 1; i <= n; ++i) {
    for (int j = i; j > 0; --j) {
        if (seq[j] < seq[i] && DP[j] >= DP[i]){
            DP[i] = DP[j] + 1;
        }
    }
}
seq는 수열의 값입니다.
for문을 반복하면서 이전 값들을 비교해서
현재값보다 작으면서 DP값이 같거나 크면
현재 DP에 작은 DP값 +1해서 넣어줍니다.

감소하는 수열은 현재값보다 크면으로만 바꿔주면 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
	int n;
	int mNum = 0;
	int seq[1010];
	int DP[1010] = { 1, };

	for (int i = 0; i < 1010; ++i) {
		seq[i] = 0;
		DP[i] = 1;
	}

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> seq[i];
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = i; j > 0; --j) {
			if (seq[j] < seq[i] && DP[j] >= DP[i]){
				DP[i] = DP[j] + 1;
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = i; j > 0; --j) {
			if (seq[j] > seq[i] && DP[j] >= DP[i]) {
				DP[i] = DP[j] + 1;
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		mNum = max(mNum, DP[i]);
	}
	
	cout << mNum << endl;

	return 0;
}