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;
}