Pagini recente » Diferente pentru newsletter/dot-com-2012 intre reviziile 2 si 7 | Cod sursa (job #1049862)
#include <iostream>
#include <fstream>
using namespace std;
ofstream out("scmax.out");
int lung_secv = 0;
int a[10001], best[10001], prec[10001], L[10001], N ;
void getData(){
ifstream in("scmax.in");
in>>N;
for (int i = 1; i <= N; ++i )
in>>a[i];
in.close();
}
int getPoz(int val){
int st = 0, dr = lung_secv;
int mij = (st+dr)/2;
while (st<=dr){
//cout<<0;
if (a[L[mij]] < val ) st = mij+1;
else dr = mij-1;
mij = (st+dr)/2;
}
return mij;
}
void putData(int val){
if (val > 0){
// cout<<4;
putData(prec[val]);
out<<a[val]<<" ";
}
}
int main(){
getData();
best[1] = L[1] = 1;
L[0] = 0;
lung_secv = 1;
int poz = 0;
//cout<<1;
//for (int i = 1; i<=N; i++)
//cout<<a[i]<<" ";
//cout<<"\n";
for (int i = 2; i<=N; ++i){
poz = getPoz(a[i]);
prec[i] = L[poz];
L[ poz+1 ] = i;
best[i] = poz+1;
//cout<<2;
if (lung_secv < poz + 1) lung_secv = poz+1;
}
int maxim = 0;
poz = 0;
for (int i = 1; i <= N; ++i)
if (maxim < best[i] ){
maxim = best[i];
poz = i;
}
out<<maxim<<"\n";
//cout<<3;
putData(poz);
out.close();
return 0;
}