2023-09-23 12:29 蚌埠坦克学院 前端工程师
关注
美团笔试9.23
第七批前端卷，第二道最长好子序列的长度有大佬写出来了么？(感觉类似力扣第300题求最长递增子序列长度)知道是动态规划，过了10%，后面想起来记录i-2下标映射应该是用数组来记录，改了一下结果到时间交卷了，也不知道改的对不对，有ac的老哥吗，想看看代码请教一下
全部评论
拧断的钥匙 楼主
楼主 蚌埠坦克学院 前端工程师
// 这是我的代码
#include <iostream>
(30316)#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
if (n < 3) {
cout << n;
return 0;
}
vector<int> a(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
int res = 2;
vector<int> dp(n);
// vector<int> idx(n); 应该把长度相同的前一个下标记录在数组里
unordered_map<int, vector<int>> m;
dp[0] = 1, dp[1] = 2;
m[0] = {-1}, m[1] = {0};
for (int i = 2; i < n; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k < m[j].size(); ++k) {
if (m[j][k] == -1 || a[m[j][k]] == a[i]) {
if (dp[j] + 1 >= dp[i]) {
dp[i] = dp[j] + 1;
m[i].push_back(j);
}
}
}
}
res = max(res, dp[i]);
}
cout << res;
return 0;
}
__default__
腾讯_开发
AC了const int MAXN = 1e4+5;
int a[MAXN], dp[MAXN][MAXN];
int int main(int argc, char const *argv[])
{
int n, ans = -1; cin >> n;
for(int i = 0; i < n; i ++){
cin >> a[i];
for(int j = 0; j < MAXN; j ++){
dp[i][j] = 1;
}
}
for(int i = 1; i < n; i ++){
for(int j = 0; j < i; j ++){
dp[i][a[j]] = dp[j][a[i]] + 1;
ans = max(dp[i][a[j]], ans);
}
}
cout << ans << endl;
return 0;
}
相关推荐
拼多多集团-PDD公司氛围 516人发布