LIS의 최적화

\(lis(i):=A_i\)를 마지막 원소로 갖는 LIS의 길이

\[lis(i)=\max_{j<i\ and\ A_j<A_i}\{lis(j)\}+1\]

단순 DP로 \(O(n^2)\)에 문제를 해결할 수 있다.

 

근데 정말로 필요한 최적의 지점만을 \(O(\log n)\)에 찾는 함수 \(f\)가 있으면 \(O(n\log n)\)에 문제를 해결할 수 있다.

\(f(i,x):=i\)단계에서 길이가 \(x\)인 LIS들의 마지막 원소들 중 최솟값

\[lis(i)=\max_{f(i-1,x)<A_i}\{x\}+1\]

근데, \(x<y\to f(i-1,x)\le f(i-1,y)\)를 만족하므로 \(\max_{f(i-1,x)<A_i}\{x\}\)를 이진 탐색으로 구할 수 있는 것이다.

\(f\)에 대한 관계식은 다음과 같다:

\[f(i,x)=\left\{\begin{matrix}f(i-1,x) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (x\neq lis(i))\\ \min(A_i,f(i-1,x)) \;\;\;\; (x=lis(i))\end{matrix}\right.\]

거창한 관계식이지만, \(i\)를 토글링시키고 \(A_i\)에 해당하는 경우만 조건에 따라 갱신시켜주면 \(O(1)\)에 전이가 가능하다.

 

 

 

 

따라서 조금 수정하면,

\(f(x):=i\)단계에서 길이가 \(x\)인 LIS들의 마지막 원소들 중 최솟값

\[lis(i)=\max_{f(x)<A_i}\{x\}+1\]

\[f(lis(i))\leftarrow \min \{f(lis(i)),A_i \} \]