
문제

풀이
- 2개의 DP배열을 만든다.
- DP_up[i]은 오른쪽부터 시작해서 점점 커지는 수열 중 i 위치에서 최대 수열의 길이를 저장한다.
- DP_down[i]은 왼쪽부터 시작해서 점점 커지는 수열 중 i 위치에서 최대 수열의 길이를 저장한다.
- 이때 최대 수열의 길이를 저장하기 위해서 부분적으로 최대값을 찾는 for 문을 수행한다.
- 마지막 결과 값은 -1을 해주어 계산한다. 그 이유는 자기 자신이 중복되어 길이가 계산되어 있지 때문이다.
코드
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int A[1001] = {0};
int DP_up[1001] = {0};
int DP_down[1001] = {0};
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
for (int i = 1; i <= N; i++) {
int maxn = DP_up[i];
for (int j = 1; j < i; j++) {
if (A[j] < A[i]) {
if (DP_up[j] > maxn) {
maxn = DP_up[j];
}
}
}
DP_up[i] = maxn + 1;
}
for (int i = N; i >= 1; i--) {
int maxn = DP_down[i];
for (int j = i; j <= N; j++) {
if (A[i] > A[j]) {
if (DP_down[j] > maxn) {
maxn = DP_down[j];
}
}
}
DP_down[i] = maxn + 1;
}
int result = DP_up[1] + DP_down[1] - 1;
for (int i = 1; i <= N; i++) {
if (result < DP_up[i] + DP_down[i] - 1) {
result = DP_up[i] + DP_down[i] - 1;
}
}
cout << result << '\n';
return 0;
}