Pagini recente » Cod sursa (job #1739082) | Cod sursa (job #1860835) | Cod sursa (job #1966270) | Cod sursa (job #1474180) | Cod sursa (job #2765585)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n;
fin >> n;
vector<int> v(n + 1);
for (int i = 1; i <= n; i++)
fin >> v[i];
vector<pair<int, int>> dp(n + 1);
int maxim = 1;
for (int i = 1; i <= n; i++) {
int best = 0;
for (int j = 1; j < i; j++) {
if (v[j] < v[i]) {
if (dp[j].first > dp[best].first) {
best = j;
}
}
}
dp[i].first = 1 + dp[best].first;
dp[i].second = best;
if (dp[i].first > dp[maxim].first)
maxim = i;
}
vector<int> sol;
int pos = maxim;
while (pos != 0) {
sol.push_back(v[pos]);
pos = dp[pos].second;
}
reverse(sol.begin(), sol.end());
fout << sol.size() << '\n';
for (auto &x : sol) {
fout << x << ' ';
}
fout << '\n';
return 0;
}