바이토닉 부분 수열의 설명을 보고 우선 오름차순과 내림차순으로 나누어 답을 찾으면 되겠다고 생각했다.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;
}