Pagini recente » Cod sursa (job #606542) | Cod sursa (job #943862) | Cod sursa (job #439996) | Cod sursa (job #2409223) | Cod sursa (job #3195638)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
#define N_MAX 100000
int v[N_MAX], dp[N_MAX], prevv[N_MAX], arr[N_MAX];
int main()
{
int n, i, j, maxd, res, respos, pos;
fin >> n;
for(i = 0; i < n; ++i) {
fin >> v[i];
}
dp[0] = 1;
res = 1;
respos = 0;
for(i = 1; i < n; ++i) {
maxd = 0;
prevv[i] = -1;
for(j = 0; j < i; ++j) {
if(v[i] > v[j]) {
if(dp[j] >= maxd) {
maxd = dp[j];
prevv[i] = j;
}
maxd = max(maxd, dp[j]);
}
}
dp[i] = maxd + 1;
if(dp[i] > res) {
res = dp[i];
respos = i;
}
}
fout << res << '\n';
pos = 0;
while(respos >= 0) {
arr[pos++] = v[respos];
respos = prevv[respos];
}
for(i = res - 1; i >= 0; --i) {
fout << arr[i] << ' ';
}
return 0;
}