python/TangDou/AcWing/DP/LIS/LCIS.md

https://blog.csdn.net/CUCUC1/article/details/113706736

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

###　前置知识

LCS

$$\LARGE f[i][j]= \left{\begin{matrix} f[i-1][j-1]+1& i,j>0,a[i]=b[j] \ max(f[i,j-1],f[i-1][j])& i,j>0,a[i]\neq b[j] \end{matrix}\right.

#### $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)

<font color='red' size=4><b>小结：</b></font>
<font color='blue' size=4><b>证明一个假设是错的很简单，直接找一个反例就行了；证明一个假设是正确的很难，因为你要证明所有情况都是对的。</b></font>


这道题目是$AcWing$ $895$. 最长上升子序列和$AcWing$ $897$. 最长公共子序列的结合版，在状态表示和状态计算上都是融合了这两道题目的方法。

状态表示：

* `f[i][j]`代表所有`a[1 ~ i]`和`b[1 ~ j]`中以`b[j]`结尾的公共上升子序列的集合；
  
* `f[i][j]`的值等于该集合的子序列中长度的最大值；

状态计算（对应集合划分）：

首先依据公共子序列中是否包含`a[i]`，将`f[i][j]`所代表的集合划分成两个不重不漏的子集：

* 不包含`a[i]`的子集，最大值是`f[i - 1][j]`；
* 包含`a[i]`的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在`b[]`中是哪个数：
  * 子序列只包含`b[j]`一个数，长度是`1`；
  * 子序列的倒数第二个数是`b[1]`的集合，最大长度是`f[i - 1][1] + 1`；
  * …
  * 子序列的倒数第二个数是`b[j - 1]`的集合，最大长度是`f[i - 1][j - 1] + 1`；

如果直接按上述思路实现，需要三重循环：
```c++
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 (a[i] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);
            f[i][j] = max(f[i][j], maxv);
        }
    }
}
```

然后我们发现每次循环求得的`maxv`是满足`a[i] > b[k]`的`f[i - 1][k] + 1`的前缀最大值。
因此可以直接将`maxv`提到第一层循环外面，减少重复计算，此时只剩下两重循环。

最终答案枚举子序列结尾取最大值即可。

时间复杂度
代码中一共两重循环，因此时间复杂度是 $O(n2)$。