[BAEKJOON] 11054 가장 긴 바이토닉 부분 수열

가장 긴 증가하는 부분수열을 

1. 아래에서 부터 위로

2. 위에서 부터 아래로

3. 두개를 더한 것의 최대

4. 자신의 값이 더해졌으니까 -1

을 해주면 된다고 한다..

이러면서 배우는 거지..

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); vector<int> Up(1001,0), Down(1001,0), input(1001); for (int j = 0; j < n; j++) scanf("%d", &input[j]); int Max; for (int x = 0; x < n; x++) { Max = 0; for (int y = 0; y < x;y++) { if (input[x] > input[y]) Max = max(Max, Up[y]); } Up[x] = Max + 1; } for (int x = n-1; x >=0; x--) { Max = 0; for (int y = n-1; y > x; y--) { if (input[x] > input[y]) Max = max(Max, Down[y]); } Down[x] = Max + 1; } Max = 0; for (int j = 0; j < n; j++) Max = max(Max, Down[j] + Up[j]); printf("%d", Max-1); return 0; }