가장 긴 바이토닉 부분 수열

수열 A가 주어질 때 가장 긴 바이토닉 부분 수열의 길이를 구하라.

바이토닉 수열이란 어떤 위치 k를 기준으로 A[1] < A[2] < ... < A[k] > A[k+1] > ... > A[n]을 만족하는 수열이다. 즉 순증가 구간 뒤에 순감소 구간이 오는 형태이다. 증가 구간 또는 감소 구간 중 하나만 있어도 바이토닉 수열로 본다.

부분 수열은 원래 수열에서 순서를 유지하며 일부 원소를 제거해 만든다.