Greatest Common Increasing Subsequence
Time Limit: 1000ms
Memory Limit: 65536kb
As a ACM/ICPC contestant, you probably have heard about Greatest Common Subsequence. And the problem here is an advanced version. We want you to calculate the length of a Greatest Common Increasing Subsequence.
A Greatest Common Increasing Subsequence is a common subsequence of two sequences keeping an ascending order. For instance, let A = 1, 4, 2, 5, -12; B = 1, 2, 4,-12. Both sequence 1, 2 or 1, 4, -12 are common subsequences but only 1, 2 is in ascending order. And it's the longest one.
The input contains multiple test cases.
Each test case starts with 2 integers N and M (1 <= N, M <= 500), indicating the length of the two sequences. Then follows with two lines of numbers indicating the sequences (each number in range (-231, 231 ) ) A line with 0 0 terminates the input.
OutputFor each test case, output the length of the Greatest Common Increasing Subsequence in a single line.
5 4 1 4 2 5 -12 -12 1 2 4 0 0