Pagini recente » Cod sursa (job #1098014) | Cod sursa (job #2396037) | Cod sursa (job #293586) | Cod sursa (job #1249977) | Cod sursa (job #3354896)
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
vector<int>parent;
vector<int>v;
vector<int>rez;
void rec(int &poz){
if(poz==-1){
return;
}
rez.push_back(v[poz]);
rec(parent[poz]);
}
int main(){
int n;
fin>>n;
v.resize(n);
for(int i=0;i<n;++i){
fin>>v[i];
}
vector<int>lung(n);
parent.resize(n);
parent[0]=-1;
for(int i=0;i<n;++i){
lung[i]=1;
for(int j=0;j<i;++j){
if(v[j]<v[i]){
if(lung[j]+1>lung[i]){
lung[i]=lung[j]+1;
parent[i]=j;
}
}
}
if(lung[i]==1){
parent[i]=-1;
}
}
int final=0;
int maxi=0;
for(int i=0;i<n;++i){
if(lung[i]>maxi){
final=i;
maxi=lung[i];
}
}
fout<<maxi<<"\n";
rec(final);
for(int i=rez.size()-1;i>=0;--i){
fout<<rez[i]<<" ";
}
return 0;
}