Cod sursa(job #1451406)

Utilizator ggokGeri Gokaj ggok Data 16 iunie 2015 22:32:42
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define mod  666013
int N,M,x;
int op;
int arr[100001];
int lis[100001];
int prev[100001];
int maxi,index;
vector<int>sol;
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
cin>>N;
for(int i=0;i<N;i++)
cin>>arr[i];

	for(int i=1;i<N;i++)
	for(int j=0;j<i;j++)
	if(arr[j]<arr[i] && lis[i]<lis[j]+1){
	lis[i]=lis[j]+1;
	prev[i]=j;
	if(lis[i]>maxi)
	maxi=lis[i],index=i;
}
//cout<<maxi<<" \n";
	while(index!=0)
	{sol.push_back(arr[index]);
		index=prev[index];
	}
	cout<<maxi+1<<"\n";
	for(int i=sol.size()-1;i>=0;i--)
	cout<<sol[i]<<" ";
	return 0;
}