最长上升子序列

nikangle · 2023-10-09 14:44:43 · 算法·理论

定义

1. 子序列：若存在一个对于长度为 n 的序列 A 的下标序列

则称序列 A_{v_1},A_{v_2}, \dots ,A_{v_k} 为序列 A 的子序列。序列 A 共有 2^n 个子序列（k 可以等于 0）。

2. 严格上升子序列：对于序列 A 的一个长度为 k 的子序列 B，如果它的所有元素严格递增，即 B_1 < B_2 < \dots <B_k，则称序列 B 为序列 A 的严格上升子序列。

3. 最长严格上升子序列（\text{LIS}）：在两个序列 A 和 B 中，长度最大的严格上升子序列的长度就是 A 与 B 的最长严格上升子序列的长度，长度为最长严格上升子序列长度的所有严格上升子序列都是 A 和 B 的最长严格上升子序列，又称二维偏序。

• 其实 \text{LIS} 模型还有其他变种，像是非严格最长上升子序列之类的，但都是只需要改一个符号，这里就不展开了。

基础题型

求最长严格上升子序列长度。

例题：洛谷B3637

用 dp_i 表示序列 A 的前 i 位以 A_i 结尾的最长严格上升子序列的长度。

考虑转移：

用另一个树状数组 cnt 记录在树状数组 cal 中到达状态 i 的方案数。

离散化后，时间复杂度 \mathcal O(n \log n)，空间复杂度 \mathcal O(n)。

Code:

int lowbit(int x){
    return x&(-x);
}
void get_max_sum(int x,int &maxn,int &num){
    num=1;
    maxn=0;
    for(;x;x-=lowbit(x)){
        if(cal[x]>maxn){
            maxn=cal[x];
            num=cnt[x];
        }
        else if(cal[x]==maxn){
            num+=cnt[x];
        }
    }
}
void modify(int x,int d,int num){
    for(;x<=n;x+=lowbit(x)){
        if(cal[x]<d){
            cal[x]=d;
            cnt[x]=num;
        }
        else if(cal[x]==d){
            cnt[x]+=num;
        }
    }
}
int main(){
    for(int i=1;i<=n;i++){
        get_max_sum(a[i]-1,maxn,num);
        modify(a[i],maxn+1,num);
        dp[i]=maxn+1;
        sum[i]=num;
    }
    get_max_sum(n,maxn,num);
    cout<<maxn<<' '<<num;
    //答案就是所有的最大值和方案数
}

困难版

序列值不同才被认为是不同的序列。

显然，选择从 A_i 目前出现的最后一个位置更新是最优的（最长上升子序列最长，方案数最多，且不重不漏）。

所以，记录每一个值 i 最后一次出现的位置 last_i，然后遍历 j(\min(A_k) \le j \le \max(A_k))，dp_i = \max (dp_{last_j}) + 1，sum_i 是所有 dp_{last_j} + 1 = dp_i 的 sum_{last_j} 和。

离散化后，时间复杂度 \mathcal O(n^2)，空间复杂度 \mathcal O(n)。

Code:

memset(last,-1,sizeof(last));
for(int i=1;i<=n;i++){
    dp[i]=1;
    last[a[i]]=i;
    for(int j=1;j<a[i];j++){
        if(last[j]!=-1){
            dp[i]=max(dp[i],dp[last[j]]+1);
        }
    }
    maxn=max(maxn,dp[i]);
    if(dp[i]==1){
        sum[i]=1;
        continue;
    }
    sum[i]=0;
    for(int j=1;j<a[i];j++){
        if(last[j]!=-1&&dp[last[j]]+1==dp[i]){
            sum[i]+=sum[last[j]];
        }
    }
}
for(int i=1;i<=n;i++){
    if(dp[i]==maxn){
      ans+=sum[i];
   }
}
cout<<maxn;

扩大数据范围：

在简单版的基础上稍作改动，每次在加方案数时减去原来的方案数即可。

离散化后，时间复杂度 \mathcal O(n \log n)，空间复杂度 \mathcal O(n)

Code:

int lowbit(int x){
    return x&(-x);
}
void getmax(int x,int &maxn,int &num){
    num=1;
    maxn=0;
    for(;x;x-=lowbit(x)){
        if(cal[x]>maxn){
            num=cnt[x];
            maxn=cal[x];
        }
        else if(cal[x]==maxn){
            num+=cnt[x];
        }
    }
}
void modify(int x,int d,int num,int _num){
    for(;x<=n;x+=lowbit(x)){
        if(d>cal[x]){
            cal[x]=d;
            sum[x]=num;
        }
        else if(d==cal[x]){
            sum[x]=sum[x]+num-_num;
        }
    }
}
int main(){
    for(int i=1;i<=n;i++){
        getmax(a[i]-1,maxn,sum);
        modify(a[i],maxn+1,sum,len[a[i]]==maxn?dp[a[i]]:0);
        dp[a[i]]=sum;
        len[a[i]]=maxn;
    }
    getmax(n,maxn,sum);
    cout<<maxn<<' '<<sum;
    return 0;
}

进阶题型 3

求最长上升子序列方案。

基础版

输出任意方案。

用 last_i 表示 dp_i 可以从 last_i 转移过来，最后递归输出答案。

时间复杂度 \mathcal O(n ^ 2)，空间复杂度 \mathcal O(n)。

Code:

void Print(int i){
    if(i==0){
        return;
    }
    Print(last[i]);
    printf("%d ",a[i]);
}
int main(){
    for(int i=1;i<=n;i++){
        dp[i]=1;
        last[i]=0;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
                last[i]=j;
            }
        }
        if(dp[i]>maxn){
            maxn=dp[i];
            w=i;
        }
    }
    Print(w);
}

困难版

输出字典序最小方案。

首先从后往前维护出序列 A_i,A_{i + 1}, \dots ,A_n 的以 A_i 开头的最长上升子序列长度 dp_i，维护方法在基础题型上稍作改动即可。

然后，枚举最长上升子序列的每一位。

若当前枚举到第 i 位，先遍历每个数在第 i - 1 次枚举选择的位置（特别的，当 i = 1 时遍历整个序列）后的第一次出现的位置 num_j（每次重新处理，不存在将为 - 1 或其他值），再按字典序从小到大枚举每个值 j，如果 j 可以选入最长上升子序列，即 dp_{num_j} = 最长上升子序列长度 - i + 1，则输出 j，更新选择的位置，并进行下一次枚举。

离散化后，时间复杂度 \mathcal O(n ^ 2)，空间复杂度 \mathcal O(n)。

Code:

for(int i=n;i>=1;i--){
    dp[i]=1;
    for(int j=i+1;j<=n;j++){
        if(a[j]>a[i]){
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    maxn=max(maxn,dp[i]);
}
cnt=0;
for(int i=1;i<=maxn;i++){
    memset(num,-1,sizeof(num));
    for(int j=cnt+1;j<=n;j++){
        if(num[a[j]]==-1){
            num[a[j]]=j;
        }
    }
    for(int j=tot+1;j<=n;j++){
        if(num[j]!=-1&&dp[num[j]]==maxn-i+1){
            printf("%d ",j);
            cnt=num[j];
            tot=j;
        }
    }
}

进阶题型 4

判断序列中的所有值分别属于以下哪种情况：

1. 一定不在最长上升子序列中。

2. 可能在最长上升子序列中。

3. 一定在最长上升子序列中。

分别维护出顺序和逆序的最长上升子序列的 \text{DP} 数组 dp1 和 dp2。

首先排除第一种情况：如果对于一个下标 i(1 \le i \le n)，若 dp1_i + dp2_i - 1 \ne 最长上升子序列长度，即用 A_i 无法组成最长上升子序列，则下标 i 属于第一种。

在后两种情况中，如果有两个及以上的下标 i 可以放在最长上升子序列的某一位，则下标 i 不一定在最长上升子序列中，如果只有一个，则一定在最长上升子序列中。

离散化后，时间复杂度 \mathcal O(n ^ 2)（树状数组 \mathcal O(n \log n)），空间复杂度 \mathcal O(n)。

因为只是求最长上升子序列处不同，本处只展示树状数组版。

Code:

int lowbit(int x){
    return x&(-x);
}
int getmax(int x){
    int ans=0;
    for(;x>0;x-=lowbit(x)){
        ans=max(ans,cal[x]);
    }
    return ans;
}
void modify(int x,int d){
    for(;x<=n;x+=lowbit(x)){
        cal[x]=max(cal[x],d);
    }
}
int main(){
    for(int i=1;i<=n;i++){
        dp1[i]=getmax(a[i]-1)+1;
        modify(a[i],dp1[i]);
        maxn=max(maxn,dp1[i]);
    }
    memset(cal,0,sizeof(cal));
    for(int i=n;i>=1;i--){
        dp2[i]=getmax(n-a[i])+1;
        modify(n-a[i]+1,dp2[i]);
    }
    memset(flag,-1,sizeof(flag));
    for(int i=1;i<=n;i++){
        if(dp1[i]+dp2[i]-1==maxn){
            cnt[dp1[i]]++;
        }
        else{
            flag[i]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(flag[i]==-1){
            if(cnt[dp1[i]]==1){
                flag[i]=2;
            }
            else{
                flag[i]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",flag[i]);
    }
    return 0;
}

总结