## Dynmamic Programming: LCIS (Longest Common Increasing Sequence)

For two sequences A and B, find length of the longest common increasing subsequence.

The length of sequence A and B does not exceed 3000.

Input format The first line contains an integer N, which represents the length of the sequence A and B.

The second row contains N integers, representing the sequence A.

The third row contains N integers, representing the sequence B.

Output format Output an integer that represents the length of the longest common increasing sequence.

data range 1 ≤ N≤ 3000, None of the numbers in the sequence exceed231− 1 Input sample:

```
4
2 2 1 3
2 1 2 3
```

Sample output:

```
2
```

State representation:

- f[i][j] is the length of LCIS in a[1 ~ i] and b[1 ~ j] ending with b[j]

State calculation:

We can first loop through i and j to get a matching pair of a[i] and b[j]. Once we have found them, we then need to find the LCIS ending with the value b[j]. We can do this by looping through all previous DP values of numbers with an array b index less than j, denoted as “k”. If the value at b[k] is less than the value of b[j], we can assume b[j] can be added to the end of the sequence and creating a new LCIS of length f[i - 1][k] + 1 (the longest possible length ending with b[k] and adding 1 for b[j]).

If implemented directly according to the above ideas, a three-fold loop is required:

```
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);
}
}
}
```

Optimization:

We can change our program from three for loops (O(N^3)) to two (O(N^2)) by realizing that we don’t need to visit all of the previous values “k” to get the maxv. Because the implementation involved is DP, for every new value of j we can reuse the previously calculated maxv value instead of looping through all previous values again in k.

The final answer enumeration subsequence ends with the maximum value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n;
int a[N], b[N];
int f[N][N];
int g[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int j = 1; j <= n; ++ j) cin >> b[j];
for (int i = 1; i <= n; ++ i) {
int maxv = 1;
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);
if (a[i] > b[j])
maxv = max(maxv, f[i - 1][j] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; ++ i) ans = max(f[n][i], ans);
cout << ans << "\n";
return 0;
}