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

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

1. 아래에서 부터 위로

2. 위에서 부터 아래로

3. 두개를 더한 것의 최대

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

을 해주면 된다고 한다..

이러면서 배우는 거지..

?

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

#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; }