Cod sursa(job #2392985)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 30 martie 2019 17:55:32
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.53 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001], t[100001], d[100001], maxi, sol, pozsol, i, j, poz, n, vsol[100001], k;
int main()
{
	f>>n;
	for(i=1;i<=n;i++) f>>v[i];
	d[1]=1;
	for(i=2;i<=n;i++){
		maxi=0;poz=0;
		for(j=1;j<i;j++)
			if(v[j]<v[i] && d[j]>maxi){
				maxi=d[j];
				poz=j;
			}
		d[i]=maxi+1;
		t[i]=poz;
		if(d[i]>sol) sol=d[i], pozsol=i;
	}
	g<<sol<<"\n";
	while(pozsol!=0){
		vsol[++k]=v[pozsol];
		pozsol=t[pozsol];
	}
	for(i=k;i>=1;i--) g<<vsol[i]<<" ";
	return 0;
}