Cod sursa(job #871241)

Utilizator dan.ghitaDan Ghita dan.ghita Data 4 februarie 2013 17:10:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream>
#include<vector>
using namespace std;
//vector<long long> v, x;
//vector<int>::iterator it;
int n, mx, pmax, s;
long long a, v[100011], x[100010];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main(){
f>>n;

for(int i=0; i<n;++i) f>>x[i], v[i]=1;//, x.push_back(a), v.push_back(1);
for(int i=n-2; i>=0;--i){
	s=0;
	for(int j=i+1; j<n; ++j)
		if(x[i]<x[j]&&s<v[j]) s=v[j];
	v[i]+=s;
	if(mx<v[i]) mx=v[i], pmax=i;
}
g<<mx<<'\n';
for(int i=pmax; v[i]>0;++i){
g<<x[i]<<' ';
int j=i+1;
while(1){
if(x[j]>x[i]&&v[j]==v[i]-1) {i=j-1; break;}
++j;
}
}
g.close();
return 0;
}