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.