# UVa 111

## Summary

This is a DP Problem - a modified Longest Increasing Subsequence. Also it can be solved as Longest Common Subsequence but LIS is more clear.

## Explanation

To find Longest Common Subsequence you can use DP: Let we have 2 sequences a[1..n], b[1..n]. And table m[0..n,0..n] were m[i,j] if the longest common subsequence of a[1..i] and b[1..j]. Then for each (i,j):

${\displaystyle m[i,j]=m[i-1,j-1]+1,a[i]=b[j]}$

${\displaystyle m[i,j]=max(m[i-1,j],m[i,j-1]),a[i]<>b[j]}$

## Gotchas

In problem you are given not exactly comparable sequences. Input "5 2 3 1 4" means that 1 must go 5th, 2 must go 2d, 3 must go 3d, 4 must go 1st and 5 must go 4th.

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

```1
2
3
```

## Input2

```10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6
```

```6
5
10
9
```