返回上一级检索目录 《动态规划（算法提高课）》

最长上升子序列模型

相关题目

模板题

AcWing 895. 最长上升子序列

AcWing 896. 最长上升子序列 II

变式与应用

AcWing 1017. 怪盗基德的滑翔翼

AcWing 1014. 登山

AcWing 482. 合唱队形

AcWing 1012. 友好城市

AcWing 1016. 最大上升子序列和

AcWing 1010. 拦截导弹

AcWing 187. 导弹防御系统

AcWing 272. 最长公共上升子序列

分析

状态转移方程
$$ f[i] = \max_{j=1}^{i-1}\{1,f[j]+1\} \quad (a[i]>a[j]) $$

代码模板

朴素版

for (int i=1; i<=n; i++) {
    f[i] = 1;
    for (int j=1; j<i; j++) {
        if (a[j] < a[i]) {
            f[i] = max(f[i],f[j]+1);
        }
    }
}

优化版

int q[N]; //q[i]表示目前所有长度为i的上升子序列中结尾的最小值
int len=0;
q[0] = -INF;
for (int i=0; i<n; i++) {
    int l=0,r=len;
    while (l < r) {
        int mid=l+r+1>>1;
        if (q[mid] < a[i]) l = mid;
        else r = mid-1;
    }
    len = max(len,r+1);
    q[r+1] = a[i];
}