1. dp (O(n^2))
对于序列中的每个元素,找到它之前比它小的数进行转移。设(dp[i])表示以第(i)个数结尾的(LIS)的长度,则转移方程:$$dp[i]=max_{jin [1,i)}(dp[j])+1$$
Code
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]&&dp[j]+1>dp[i])dp[i]=dp[j]+1;
}
}
2. 栈+二分 (O(nlog n))
我们模拟一个栈(S)。对于一个元素(a_i),如果它大于栈顶元素,则将其压入栈中;否则,二分查找栈中第一个比它大的元素(S_j),然后将(S_j)换成(a_i)。那么,栈顶指针(top)即为(LIS)的长度。
Code
1.
for(int i=1;i<=n;i++){
if(a[i]>S[top])S[++top]=a[i];
else{
int l=1,r=top,mid;
while(l<=r){
mid=(l+r)>>1;
if(S[mid]<a[i])l=mid+1;
else r=mid-1;
}
S[l]=a[i];
}
}
2.
for(int i=1;i<=n;i++){
if(a[i]>S[top])S[++top]=a[i];
else{
int t=upper_bound(S+1,S+top+1,a[i])-S;
S[t]=a[i];
}
}
3. 数据结构 (O(nlog n))
使用线段树或树状数组维护最大值。