공룡발자국 Knuth Opt로 잘못접근한것에서 착안  

 

점 N개가 주어졌을 때, 가장 긴 산맥을 구하는 문제

 

산맥의 정의: m개의 점(단, m은 홀수)으로 이루어져 있으며, v[i].x < v[i+1].x이고, v[1]은 극대점, v[2]는 극소점...v[m-1]은 극대점이면 산맥이다

 

나이브 DP: 스위핑 느낌으로 가던지 구간DP 쪼개기(= Knuth)로 가던지 O(N^2)정도  

최적화: 스위핑으로 NlogN 가능할 듯