Pagini recente » Cod sursa (job #269496) | Cod sursa (job #11203) | Cod sursa (job #863703) | Cod sursa (job #789240) | Cod sursa (job #1524810)
#include <iostream>
#include <fstream>
using namespace std;
struct trii {
int val,best,pre ;
};
trii v[100001];
int n ;
void Afisare(int ind);
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
scanf("%d",&n);
for(int i = 0; i<n; i++) {
scanf("%d",&v[i].val);
v[i].best = v[i].pre = -1;
}
v[0].best = 1;
int maxim = 1, maxIndex = 0;
int best, index ;
for ( int i = 1;i < n; i++ ) {
best = 0; index = -1;
for (int j = i-1; j >= 0 ; j--) {
if (v[j].val < v[i].val && v[j].best > best) {
best = v[j].best;
index = j;
}
}
v[i].best = best + 1;
v[i].pre = index;
if (v[i].best > maxim) {
maxIndex = i;
maxim = v[i].best;
}
}
int i = maxIndex , k = 1;
while (v[i].pre != -1 ) {
i = v[i].pre ;
k++;
}
printf("%d \n",k);
Afisare(maxIndex);
fclose(stdin);
fclose(stdout);
return 0;
}
void Afisare(int ind) {
if (v[ind].pre == -1) {
printf("%d ",v[ind].val);
return;
}
Afisare(v[ind].pre);
printf("%d ",v[ind].val);
}