Problem 75: Longest Common Increasing Subsequence

Problem Statement: Given two sequences, find the length of the longest subsequence that is common to both and is strictly increasing.

Input

The first line contains an integer n followed by n integers (first sequence). The next line contains an integer m followed by m integers (second sequence).

Output

Print the length of the longest common increasing subsequence.

Examples


Input:
5 1 3 2 4 5
6 1 2 3 4 5 6

Output:
4

Solution Explanation

For each element in the first sequence, use DP to find the longest increasing subsequence that is also present in the second sequence. A nested loop with binary search optimization may be applied.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    int n; 
    cin >> n;
    vector A(n);
    for(int i = 0; i < n; i++) 
        cin >> A[i];
    int m; 
    cin >> m;
    vector B(m);
    for(int i = 0; i < m; i++) 
        cin >> B[i];
    vector dp(m, 0);
    for(int i = 0; i < n; i++){
        int current = 0;
        for(int j = 0; j < m; j++){
            if(A[i] == B[j] && current + 1 > dp[j]){  
                dp[j] = current + 1;
            }
            if(B[j] < A[i]){
                current = max(current, dp[j]);
            }
        }
    }
    int ans = 0;
    for(auto v : dp) ans = max(ans, v);
    cout << ans << "\n";
    return 0;
}