LCIS-最长公共上升子序列

佚名 6年前 (2019-04-18) 随笔 1440人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

LCS最长公共子序列 for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } LIS最长上升子序列 for(int i=2; i<=n; i++) for(int j=1; j<i; j++) { if(a[i]>a[j]) f[i]=max(f[i],f[j]+1); ans=max(ans,f[i]); } // 例题：LCIS，O(N^3)
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i] == b[j]) { for (int k = 0; k < j; k++) if (b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1); } else f[i][j] = f[i - 1][j]; // 例题：LCIS，O(N^2)
for (int i = 1; i <= n; i++) { // val是决策集合S(i,j)中f[i-1][k]的最大值
    int val = 0; // j=1时，0可以作为k的取值
    if (b[0] < a[i]) val = f[i - 1][0]; for (int j = 1; j <= m; j++) { if (a[i] == b[j]) f[i][j] = val + 1; else f[i][j] = f[i - 1][j]; // j即将增大为j+1，检查j能否进入新的决策集合
        if (b[j] < a[i]) val = max(val, f[i - 1][j]); } }