LCIS：最长公共上升子序列

LCIS：最长公共上升子序列

法一：时间复杂度O(n^3)

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

/* 

*/
const int N = 3010;

int n;
int a[N],b[N];
int f[N][N];

/*

状态表示：f(i,j)：a串前i个与b串前j个，以b[j]结尾的max公共长度 

状态转移方程：
        首先选择公共部分： 
            不选择a[i],f[i][j] = f[i - 1][j];
            选择a[i](a[i] == b[j])
            ：选择最长
            k∈(1,j - 1)求最长上升子序列长度
初始化：
    公共(前i个一定包含前i-1)：    f[i][j] = f[i - 1][j];
    上升长度(自身)：    f[i][j] = 1;              

*/
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) cin >> b[i];
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j]){
                f[i][j] = 1;
                for(int k = 1; k < j; k ++ ){
                    if(b[k] < b[j]){
                        f[i][j] = max(f[i][j],f[i][k] + 1);
                    }
                }
            } 
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res,f[n][i]);
    cout<<res;
    return 0;
}

法二：时间复杂度：O(n^2)

• maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值
• 将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环

  int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) cin >> b[i];
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            int maxv = 1;
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j]) maxv = max(maxv,f[i][j]);
            if(b[j] < a[i]) maxv = max(maxv,f[i][j] + 1);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res,f[n][i]);
    cout<<res;
    return 0;
  }