Pagini recente » Cod sursa (job #2042675) | Cod sursa (job #1789033) | Cod sursa (job #361213) | Cod sursa (job #1940395) | Cod sursa (job #2971848)
#include <bits/stdc++.h>
unsigned int v[100005], dp[100005];
std :: vector <int> ans;
int main() {
std :: ios_base :: sync_with_stdio(0);
std :: ifstream fin("scmax.in");
int n, i;
fin >> n;
for (i = 1; i <= n; ++ i)
fin >> v[i];
fin.close();
dp[1] = 1;
unsigned int maxx, j;
for (i = 2; i <= n; ++ i) {
maxx = 0;
for (j = 1; j < i; ++ j)
if (v[j] < v[i])
maxx = std :: max(maxx, dp[j]);
dp[i] = maxx + 1;
}
int pos = 1;
for (i = 2; i <= n; ++ i)
if (dp[pos] < dp[i])
pos = i;
std :: ofstream fout("scmax.out");
fout << dp[pos] << '\n';
int next_pos;
ans.push_back(v[pos]);
while (dp[pos] > 1) {
next_pos = pos;
for (i = pos - 1; i > 0; -- i)
if (dp[i] + 1 == dp[pos] and v[i] < v[pos]) {
next_pos = i;
break;
}
pos = next_pos;
ans.push_back(v[pos]);
}
while (!ans.empty()) {
fout << ans.back() << ' ';
ans.pop_back();
}
fout.close();
return 0;
}