Pagini recente » Cod sursa (job #2604586) | Cod sursa (job #557742) | Cod sursa (job #1945209) | Cod sursa (job #811017) | Cod sursa (job #1015922)
#include <cstdio>
using namespace std;
int n;
int sir[100005]; //sirul de elemente
int L[100005]; //sirul in care salvam subsirul maximal
int urm[100005];
int ind_max;
void citire(){
scanf("%d\n",&n);
for(int i=0;i<n;++i)
scanf("%d ",&sir[i]);
}
void rezolvare(){
L[n-1]=1;
urm[n-1]=n-1;
for(int i=n-2;i>=0;--i){
urm[i]=i;//retine pozitia maximului din secventa i+1,n
L[i]=0;
for(int j=i+1;j<n;++j)
if(sir[i]<sir[j] && L[urm[i]]< L[j])
urm[i]=j;
L[i]= L[urm[i]]+1;
if(L[i]>L[ind_max])
ind_max=i;
}
}
void afisare(){
printf("%d\n",L[ind_max]);
int i=ind_max;
while(i!=urm[i]){
printf("%d ",sir[i]);
i=urm[i];
}
printf("%d ",sir[i]);
}
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
citire();
rezolvare();
afisare();
return 0;
}