문제 : https://www.acmicpc.net/problem/11054
먼저 증가하는 수열의 최대 길이와 감소하는 수열의 최대 길이를 구해주었습니다.
그 후 각 자리의 최대 길이를 서로 더해준 후 max 값을 비교하여 해결했습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include <iostream> #include <algorithm> #include <vector>
using namespace std;
int main() { int max_value = 0; int n; cin >> n; vector<int> a(n);
for (int i = 0; i < n; i++) { cin >> a[i]; }
vector<int> plus(n); vector<int> minus(n);
for (int i = 0; i < n; i++) { plus[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && plus[i] < plus[j] + 1) { plus[i] = plus[j] + 1; } } }
for (int i = n-1; i >= 0; i--) { minus[i] = 1; for (int j = n-1; j > i; j--) { if (a[j] < a[i] && minus[i] < minus[j] + 1) { minus[i] = minus[j] + 1; } } }
for (int i = 0; i < n; i++) { max_value = max(max_value, plus[i] + minus[i] - 1); }
cout << max_value << '\n';
return 0; }
|