# Cod sursa(job #2549472)

Utilizator Data 17 februarie 2020 18:37:31 Subsir crescator maximal 100 cpp-64 done Arhiva educationala 1.35 kb
``````#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 1e5 + 1;

int dp[NMAX]; /// Valoare minima a unui element pe care se termina un subsir de lungime i
int v[NMAX];
int rez[NMAX];
int afisare[NMAX];

int cb( int st, int dr, int val ) {
int mij;
while ( st < dr - 1 ) {
mij = ( st + dr ) / 2;
if ( v[dp[mij]] < val )
st = mij;
else
dr = mij;
}
return st;
}

int main() {
ifstream fin( "scmax.in" );
ofstream fout( "scmax.out" );
int n, i, maxim, poz, j;
fin >> n;
for ( i = 1; i <= n; i ++ ) {
fin >> v[i];
}
dp[1] = 1;
rez[1] = 0;
maxim = 1;
for ( i = 2; i <= n; i ++ ) {
poz = cb( 0, maxim + 1, v[i] );
if ( dp[poz + 1] != 0 ) {
if ( v[dp[poz + 1]] <= v[i] ) {
///dp[poz + 1] = dp[poz + 1];
} else {
dp[poz + 1] = i;
rez[i] = dp[poz];
}
} else {
maxim ++;
rez[i] = dp[poz];
dp[poz + 1] = i;
}
}
fout << maxim << '\n';
i = dp[maxim];
j = 0;
while ( i > 0 ) {
afisare[j ++] = v[i];
i = rez[i];
}
for ( j --; j >= 0; j -- ) {
fout << afisare[j] << ' ';
}
return 0;
}
``````