이지코딩

바이토닉 부분 수열이란, 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족 하는 수열이다. 예를 들면 {10, 20, 30, 10} 은 30을 기준으로 위 식을 만족하기에 바이토닉 부분수열 이라고 할 수 있지만, {10, 20, 30, 10, 20}은 20으로 인해 바이토닉 부분 수열이 아니다. 자 이제 가장 긴 바이토닉 부분 수열을 찾기 위한 작업을 알아보자. 가장 긴 바이토닉 부분 수열을 찾기 위해서는 첫번째, 자기 자신까지 증가하는 가장 긴 증가수열의 길이. 두번째,자기 자신부터 감소하는 가장 긴 감소수열의 길이. 를 알아야 할 것이다. 이를 모두 구한 후, 자기 자신이 중복 되므로, 두 수열의 길이의 합에서 1을 빼주면 ..