# Cod sursa(job #2551512)

Utilizator Data 19 februarie 2020 21:31:04 Subsir crescator maximal 70 cpp-64 done Arhiva educationala 2.22 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int NMAX=100010;

int n,poz[NMAX];
vector<pair<int,int> >v;
int initial[NMAX];
int sol[NMAX];
int aib[NMAX];
int ind[NMAX];
int pre[NMAX];
int stiva[NMAX];
struct comparator{
bool operator()(pair<int,int> a, pair<int,int> b){
return a.first<b.first;
}
};
void citire()
{
fin>>n;
v.reserve(NMAX);
v.push_back(pair<int,int>(0,0));
pair<int,int> cont;
for (int i=1; i<=n; i++){
fin>>cont.first;
cont.second=i;
v.push_back(cont);
}
}
void salvare()
{
for (int i=1; i<=n; i++)
initial[i]=v[i].first;
}
void stabilirePozitii()
{
for (int i=1; i<=n; i++){
poz[v[i].second]=i;
int j=i+1;
while (j<=n){
if (v[i].first==v[j].first){
poz[v[j].second]=i;
j++;
}else{
break;
}
}
i=j-1;
}
}
pair<int,int> query(int j)
{
int maxim=0, pozMx=-1;
while (j>0){
if (aib[j]>maxim){
maxim=aib[j];
pozMx=ind[j];
}
j-=(j&(~(j-1)));
}
return pair<int,int>(maxim,pozMx);
}
void update(int i,int val,int indice)
{
while (i<=n && val>aib[i]){
aib[i]=val;
ind[i]=indice;
i+=(i&(~(i-1)));
}
}
void rezolvare()
{
pair<int,int> rezultat;
for (int i=1; i<=n; i++){
rezultat=query(poz[i]-1);
sol[i]=rezultat.first+1;
pre[i]=rezultat.second;
update(poz[i],sol[i],i);
}
}
void afisare()
{
int mx=0,pozMx=-1;
for (int i=1; i<=n; i++){
if (sol[i]>mx){
mx=sol[i];
pozMx=i;
}
}
fout<<mx<<'\n';
while (pozMx!=-1){
stiva[0]++;
stiva[stiva[0]]=pozMx;
pozMx=pre[pozMx];
}
for (int i=stiva[0]; i>=1; i--)
fout<<initial[stiva[i]]<<' ';
}
int main()
{
citire();
salvare();
sort(v.begin()+1,v.end(),comparator());
stabilirePozitii();
rezolvare();
afisare();
}
``````