动态规划：LCIS

先给出状态转移方程：

定义状态
F[i][j]表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度
状态转移方程：
①F[i][j] = F[i-1][j] (a[i] != b[j])
②F[i][j] = max(F[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])

这个可以优化到O（n^2）的时间复杂度，然后再滚动数组一下，空间复杂度就可以是O（n）的，这里直接给出最优实现策略

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn=3005;
 5 int n1,n2;
 6 int a[maxn],b[maxn],f[maxn];
 7 int main()
 8 {
 9     scanf("%d",&n1);
10     n2=n1;
11     for(int i=1;i<=n1;i++) scanf("%d",&a[i]);
12     for(int j=1;j<=n2;j++) scanf("%d",&b[j]);
13     int tmp;
14     for(int i=1;i<=n1;i++)
15     {
16         tmp=0;
17         for(int j=1;j<=n2;j++)
18         {
19             if(a[i]>b[j]&&tmp<f[j]) tmp=f[j];
20             if(a[i]==b[j]) f[j]=tmp+1;
21         }
22     }
23     tmp=0;
24     for(int i=1;i<=n2;i++)
25         if(tmp<f[i]) tmp=f[i];
26     printf("%d
",tmp);
27     return 0;
28 }

比SAM简单多了