백준 11054: 가장 긴 바이토닉 부분 수열(DP)

nlogn으로 풀어본다고 개삽질하다가 지쳐서

n2으로 무식하게 오름차순 내림차순 다 계산해서 배열에 때려박은다음

계산된 배열 두개중 합친 값이 가장 큰걸 반환하게 했다.

솔찍히 시간초과 날줄알앗는데 으..응?으응???하니까 정답입니다!!...

아몰라 ㄹ풀었음댓지머

#include <iostream>
 
int seq[1010];
int highDp[1010];
int lowerDp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = highDp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && highDp[j] > m)
                m = highDp[j];
        highDp[i] = m + 1;
        
    }
 
    for (int i = N; i >= 1; --i)
    {
        int m = 0;
        for (int j = N + 1; j >= i; --j)
            if (seq[i] > seq[j] && lowerDp[j] > m)
                m = lowerDp[j];
        lowerDp[i] = m + 1;
    }
 
    int mx = 0;
    for (int i = 0; i <= N; ++i)
    {
        mx = lowerDp[i] + highDp[i] < mx ? mx : lowerDp[i] + highDp[i];
    }
    std::cout << mx - 1;
    return 0;
}
 

으으 왤캐 깔끔하게 안풀리지?