https://www.acmicpc.net/problem/11504

D1[i] = A[i]를 포함하는 LIS의 길이(A[0] to A[i]에서 생각)

D2[i] = A[i]를 포함하는 LDS의 길이(A[i] to A[N-1]에서 생각)

라고 할 때, D1[i]+D2[i]-1의 최댓값이 구하고 싶은 문제의 답입니다.

N이 1000이라 느긋하게 N^2 알고리즘으로 LIS, LDS의 길이를 구했지만 시간제한이 빡빡했다면 세그먼트 트리나 이진탐색을 활용해 NlgN으로 LIS, LDS의 길이를 구했을 것입니다.

https://github.com/encrypted-def/BOJ/blob/master/11504.cpp