最长公共上升子序列(LCIS)

前置知识

1. LCS
   

2. LIS

注意：

  刚开始看这个问题的时候，第一反应是先求出LCS再求出LCS的LIS，事实上这是有问题的，我们并不能保证这么求出的LCIS是最长的,比如下面这个例子

Example
a:7 1 5 6 4 2 7
b:7 1 5 4 6 7 2
按照递归的取“最长公共子序列”,取出：
7 1 5 6 2
此序列的“最长上升子序列”为：
1 5 6 (len=3)
但原序列的“最长公共上升子序列”为：
1 5 6 7 (len=4)

求解

 设第一个串为a，第二个串为b

1. 首先确定dp状态f[i, j],表示前a串前i个字符和b串前j个字符且以b[j]为结尾的LCIS
2. 状态方程：
   对于当处于(a[i], b[j]) 状态时 ,由于dp状态就决定了，b[j]是一定作为这个状态下LICS的结尾的，所以对于a[i]，就有两种情况，将其纳入LCIS或者不纳入，首先先说不讲a[i]纳入LCIS的情况
   （1）若是 a[i] != b[j] ，显然是一定不能讲a[i]与b[j]进行配对的，那么问题就缩小成了前a的前i - 1个字符与b的前j个字符且以b[j]结尾的LCIS，即f[i - 1, j]也就是说 ，i之前的以b[j]结尾的序列自然没有改变，仍然是长度仍然是f[i−1][j]; 若是a[i] == b[i] 如果不想要a[i]与b[j]进行配对，是不是也会得到上面的结果，故当
   不讲a[i]与b[j]配对(或无法配对)时，f[i, j] = f[i - 1, j]

（2）当a[i] == b[j]且它们进行配对时，就要在a串前i - 1个字符和b的前j - 1个字符中找到一个最长的序列，设这个序列以t结尾且b[t] < b[j]，是不是就等价于
f[i, j] = max(f[i - 1, t]) + 1 (t > 0 && t < j && b[t] < b[j])

这样就把这个问题可以转化为最优子结构的问题，且得到状态转移方程如下

				f[i - 1, j]    (a[i] != b[j])
f[i, j] = 
				max(f[i - 1, t]) + 1   (t > 0 && t < j && b[t] < b[j]) (a[i] == b[j])

讲上述思路转化为代码

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])
        {
            int maxv = 1;
            for (int k = 1; k < j; k ++ )
                if (b[j] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);
            f[i][j] = max(f[i][j], maxv);
        }
    }
}

 上面代码的时间复杂度为O(n ³)，是很不理想的，可以对其进行等价转化为O(n ²)的优化
观察第三层循环，可以发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。，而且是在a[i] == b[j]的时候成立，且可以发现，在每一次进行第二层循环时，a[i]是不变的，这也就可以推出，与a[i]进行配对的b[j]的值也是暂时不变的，那么把b[j]等价转化为a[i],并将maxv提至第一层循环内，在每一次比较a[i]和b[j]时，一起讲maxv处理出来，这样就可以将其优化为如下的O(n ²)的代码

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

这样其实已经够了，但是追求优化的话，还可以进行空间的优化，不难发现，每一次都止利用了上一层的结果，那么可以采用滚动数组的方法进行空间优化

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

acwing 272 最长公共上升子序列

#include <iostream>

using namespace std;

const int maxn = 3e3 + 5;

int f[maxn], a[maxn], b[maxn];
int n, ans;

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++) {
        int maxv = 0;
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) f[j] = max(f[j], maxv + 1);
            if (a[i] > b[j]) maxv = max(maxv, f[j]);        
            ans = max(f[j], ans);
        }
    }
    cout << ans << endl;
    return 0;
}