가장 긴 바이토닉 부분수열

---

문제

---

실수한 부분

가장 긴 증가하는 부분 수열과 유사한 문제이다.
다른점은 감소하는 부분 수열도 구해서 가장 긴 수열을 구하는 것이다.
감소하는 수열에서 고민을 하다가 구현을 하였는데, 인덱스 구현부에서 실수하다가 재시도 횟수를 늘렸다.
감소하는 수열이니, 끝의 배열 인덱스 값보다 큰 것을 감소하는 양 구현을 했었는데, 그 부분이 큰 실수였다.
그를 토대로 구현하려면 입력된 배열의 최대값부터 감소하여 탐색해야 하는데, 그 생각을 흘려보내서 한동안 계속 실패했다.

구현

증가하는 부분 수열과 감소 부분 수열을 2개의 DP로 구현했다. 그 후, 배열의 인덱스와 매칭하기 위해 따로 배열을 만들어 넣어주었으며, 마지막에 그 배열을 전체 탐색해서 더한, 가장 긴 바이토닉 수열 길이를 출력한다.

#include<iostream>

        using namespace std;
        
        int arr[1001];
        int dp[1001];
        int re_dp[1001];
        int SaveArr[2][1001];
        
        int main() {
            int n;
            scanf_s("%d", &n);
        
            for (int i = 0; i < n; i++) {
                scanf_s("%d", &arr[i]);
            }
            for (int i = 0; i < n; i++) {
                int Asc = 0, Desc = 0;
                int AVal = arr[i], DVal = arr[n - 1 - i];
        
                for (int j = 1; j < arr[i]; j++) { //증가 수열
                    if (dp[j] > Asc)
                        Asc = dp[j];
                }
        
                dp[AVal] = Asc + 1;
                SaveArr[0][i] = dp[AVal];
        
                for (int j = 1; j < arr[n - 1 - i]; j++) {
                    if (re_dp[j] > Desc)
                        Desc = re_dp[j];
                }
        
                re_dp[DVal] = Desc + 1;
                SaveArr[1][n - 1 - i] = re_dp[DVal];
            }
            int ans = 0;
        
            for (int i = 0; i < n; i++)
                ans = ans > SaveArr[0][i] + SaveArr[1][i] ? ans : SaveArr[0][i] + SaveArr[1][i];
        
            printf("%d", ans - 1);
        }