이제 주가 스팬 문제로 돌아가 보자. 앞에서 O(n(n + 1/2))의 복잡도를 갖는 알고리즘을 찾았다. 이는 지금까지 설명한 복잡도에 따르면 O(n²)와 같다. 더 잘할 수 있을까? 그림 1-1로 돌아가 보자. 여섯째 날일 때 첫째 날에 다다를 때까지 주가를 이전 모든 날과 비교할 필요가 없다. 우리는 모든 날을 거쳐왔기 때문에 둘째 날과 셋째 날, 넷째 날, 다섯째 날은 모두 주가가 여섯째 날과 같거나 작음을 이미 알고 있다. 어떻게든 이 정보를 유지한다면 이 모든 날과 비교하는 대신에 오직 첫째 날만 비교하면 된다.

이것은 일반적 패턴인데, k일에 있다고 상상해 보라. (k - 1)일의 주가가 k일의 주가보다 낮거나 같으면, 즉 quotes[k - 1] ≤ quotes[k] 또는 quotes[k] ≥ quotes[k - 1]이면 다시 (k - 1)과 비교할 이유가 없다. 왜? 미래의 어느 날인 (k + j)일에 있다고 해 보자. (k + j)일의 주가가 k일의 주가보다 낮으면, 즉 quotes[k + j] ＜ quotes[k]면 (k + j)일에 시작하는 스팬은 k일에서 끝나기 때문에 (k - 1)일과 비교할 필요가 없다. (k + j)의 주가가 k의 주가보다 높다면 quotes[k + j] ≥ quotes[k]이고, quotes[k] ≥ quotes[k - 1]이므로 quotes[k + j] ≥ quotes[k - 1]이 된다. 따라서 스팬의 끝을 역으로 찾을 때마다 조사하는 날보다 낮거나 같은 값인 날들을 모두 제외한다. 그리고 미래 어느 날의 스팬에서도 이미 제외한 날들은 고려 대상에서 배제할 수 있다.