백준 11054 가장 긴 바이토닉 부분 수열 (C++)

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

바이토닉 부분 수열의 설명을 보고 우선 오름차순과 내림차순으로 나누어 답을 찾으면 되겠다고 생각했다.asc와 des로 나누어 부분 수열의 오름차순과 내림차순의 길이를 dp를 활용해 구해주었다. 그 후 두 길이의 합이 가장 큰 값을 구해 겹치는 부분을 제거하여 값을 구했다.
오랜만에 dp 문제라 그런지 생각이 잘 나지 않았다. 관련 문제들을 더 풀어봐야겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, res = 0;
int A[1001];
int dp1[1001];
int dp2[1001];

void des() {
	for (int i = N - 1; i >= 0; i--) {
		dp2[i] = 1;
		for (int j = N - 1; j >= i; j--) {
			if (A[j] < A[i] && dp2[i] < dp2[j] + 1) {
				dp2[i] = dp2[j] + 1;
			}
		}
	}
}

void asc() {
	for (int i = 0; i < N; i++) {
		dp1[i] = 1;
		for (int j = 0; j <= i; j++) {
			if (A[j] < A[i] && dp1[i] < dp1[j] + 1) {
				dp1[i] = dp1[j] + 1;
			}
		}
	}
}

void solution() {
	asc();
	des();

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	solution();
	
	return 0;
}