给出1,2,…,n 的两个排列P1 和P2 ,求它们的最长公共子序列。
第一行是一个数 n。
接下来两行,每行为 n 个数,为自然数 1,2,…,n 的一个排列。
一个数,即最长公共子序列的长度。
输入 #1
5
3 2 1 4 5
1 2 3 4 5
输出 #1
3
思路:
代码:
class Solution {
public:
int lengthOfLIS(vector
int n=(int)nums.size();
if (n == 0) return 0;
vector
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
手机扫一扫
移动阅读更方便
你可能感兴趣的文章