Wavio란 정수의 수열의 일종이다. 이는 아래와 같은 재미있는 특성을 갖추고 있다.

Wavio인 수열은 홀수의 길이를 가진다. L=2*n+1 (L:길이) 앞의 (n+1)개의 정수는 오름차순 순이다. 뒤의 (n+1)개의 정수는 내림차순 순이다. Wavio를 이루는 수열 안의 인접한 두 개의 정수는 같을 수 없다.

예를 들어 1, 2, 3, 4, 5, 4, 3, 2, 0은 길이 9의 wavio 수열이다. 하지만 1, 2, 3, 4, 5, 4, 3, 2, 2는 wavio 수열이 아니다.

이번에 풀어야할 문제는 정수의 수열이 주어졌을 때, 수열을 이루는 부분 수열 중에서 가장 긴 wavio 수열을 찾는 것이다. 예로 들어서 다음과 같은 정수의 수열이 주어졌다고 하자.

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

위의 경우에서 가장 긴 wavio 수열은 다음과 같다. : 1 2 3 4 5 4 3 2 1. 따라서 출력해야 하는 길이는 9이다.

wavio sequence timer 1s memory 64MB

wavio sequence 1s 64MB