Question
Longest Common Increasing Subsequence - LCIS
You are given two integer arrays nums1 and nums2 of sizes n and m respectively.
Your task is to determine the length of the Longest Common Increasing Subsequence (LCIS) — that is, the maximum length of a strictly increasing sequence that appears as a subsequence in both arrays.
A subsequence does not need to be contiguous, but the order of elements must be maintained in both of the arrays.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the sizes of the arrays - KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
The third line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
The third line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
Output
Output the length on the longest common increasing subsequence of the two arrays nums1 and nums2.
Example
Input
5 5
5 1 6 2 7
1 2 5 7 6
Output
3
Explanation
The LCIS is: 1, 2, 7
It appears in increasing order.
It appears as a subsequence in both arrays.
Thus, the answer is 3.
Input
8 6
2 1 4 3 5 7 6 9
1 8 3 4 5 9
Output
4
Explanation
The possible LCIS for these arrays are: 1, 3, 5 , 9 and 1, 4, 5, 9.
They are strictly increasing.
They appear as a subsequence in both arrays.
Thus, the answer is 4.
5 5
5 1 6 2 7
1 2 5 7 6
Output
3
Explanation
The LCIS is: 1, 2, 7
It appears in increasing order.
It appears as a subsequence in both arrays.
Thus, the answer is 3.
Input
8 6
2 1 4 3 5 7 6 9
1 8 3 4 5 9
Output
4
Explanation
The possible LCIS for these arrays are: 1, 3, 5 , 9 and 1, 4, 5, 9.
They are strictly increasing.
They appear as a subsequence in both arrays.
Thus, the answer is 4.