가장 긴 증가하는 부분 수열 5

문제 링크

문제를 읽은 당신은 이게 이전 문제랑 뭐가 다른건지 어리둥절하다. 하지만 수많은 문제를 겪어온 당신은 침착하게 입력 제한을 파악하기 시작한다. ‘그럴 줄 알았다’. 지금까지 배운 LIS 알고리즘들은 시간 복잡도가 $O(N^2)$이다. 그런데 이번 문제의 $N$ 최댓값은 무려 $10^6$이다. 복잡도가 $N^2$인 알고리즘을 사용하면 약 1조번의 연산을 하게 된다. 그렇다. 이 문제를 해결하기 위해서는 새로운 알고리즘을 적용시켜야 한다.

발상

점화식