수열에서 임의의 개수의 숫자를 뽑아, 그 순서대로 나열한 연속된 숫자들의 차이가

양의 값과 음의 값으로 반복되어지는 수열을 지그개그 수열이라고 한다.

첫 번째의 지그재그 수열의 차이는 양의 값이나, 음의 값이 될 수 있다.

단순히 하나의 숫자만 존재할 경우에도, 이것 역시 1개의 지그재그 수열이다.

예를 들면 1, 4, 5, 7, 4, 0, 9, 2, 5, 5 에서 1, 7, 4, 9, 2, 5의 수를 뽑아

수열의 순서대로 나열한 다음 각각의 차이를 수열로 나타내면 (6, -3, 5, -7, 3)으로,

양의 값과 음의 값이 반복되므로 6개의 길이를 가진 지그재그 수열이라고 할 수 있다.

하지만 1, 7, 4, 5, 5를 뽑았을 경우 (6, -3, 1, 0)으로

마지막의 차이가 0 이 되어 음의 값이 되지 않았으므로 이는 지그재그 수열이 아니다.

임의의 개수의 수열이 주어졌을 때, 가장 긴 지그재그 수열의 길이를 출력하는 프로그램을 작성하시오.

지그재그 수열1 timer 1s memory 256MB

지그재그 수열1 1s 256MB