오래된 글이지만 고민했던 걸 공유하기 위해 적습니다.

문제에서 개는 최대 지점을 찾아가니까 반대로 작은 값부터 방문하는 것이 옳습니다.

만약 큰 값부터 방문한다면 중간에 어떤 새로운 경로를 찾아 갱신할 때, 개가 있을만한 최대 지점이 어딘 지 찾을 수 없게 됩니다.

새로운 경로를 찾긴 했는데 그 중 최대 지점이 지금까지 지나온 점들 중에 있을지, 아니면 완전히 경로가 새로 짜여서 아예 다른 최대 지점이 나오는지 구분할 방법이 없죠.

반대로 작은 값부터 방문한다면 새로 갱신한 경로도 반드시 지금보다 작은 값들로 이루어져 있다는 것이 보장됩니다. (모든 경로의 처음, 끝 점을 뺀 중간 지점들은 무조건 현재 방문 값보다 작음)

따라서 개가 있을 곳은 처음, 끝, 현재 방문중인 점 << 이 3개 중에 한 개일 수 밖에 없습니다.

이게 핵심 로직이므로 순서는 반드시 작은 값부터 방문해야 합니다.