Cod sursa(job #1967928)
Utilizator | Petru Trimbitas S7012MY | Data | 17 aprilie 2017 12:30:41 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
#include <algorithm>
#include <map>
#define DN 100005
using namespace std;
int n,v,vmin[DN],r;
map<int,int> lst;
ifstream f("scmax.in");
ofstream g("scmax.out");
void pr(int r) {
if(!r) return;
pr(lst[r]);
cout<<r<<' ';
}
int main() {
f>>n;
for(int i=1; i<=n; ++i) vmin[i]=(1<<30);
for(int i=1; i<=n; ++i) {
f>>v;
int pz=lower_bound(vmin,vmin+n,v)-vmin;
if(pz) {
lst[v]=vmin[pz-1];
vmin[pz]=v;
r=max(r,pz);
}
}
g<<r<<'\n';
pr(vmin[r]);
}