Pagini recente » Cod sursa (job #3199865) | Cod sursa (job #1090251) | Cod sursa (job #3216139) | Cod sursa (job #2753836) | Cod sursa (job #2972308)
#include <iostream>
#include <vector>
#define MAXN 100003
using namespace std;
int N, a[MAXN], d[MAXN], pre[MAXN];
int main()
{
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> a[i];
}
d[1] = 1;
pre[1] = -1;
for(int i = 2; i <= N; i++) {
int besti_val = 0, besti = -1;
for(int j = 1; j < i; j++) {
if(a[j] < a[i]) {
if(besti_val < d[j]) {
besti_val = d[j];
besti = j;
}
}
}
d[i] = besti_val + 1;
pre[i] = besti;
}
int imax = 1, maxval = 0;
for(int i = 1; i <= N; i++) {
if(d[i] > maxval) {
maxval = d[i];
imax = i;
}
}
cout << d[imax] << endl;
int i = imax;
vector<int> R;
while(i != -1){
R.push_back(a[i]);
i = pre[i];
}
for(auto it = R.rbegin(); it != R.rend(); it++) {
cout << *it << " ";
}
return 0;
}