Pagini recente » Cod sursa (job #413682) | Cod sursa (job #434338) | Cod sursa (job #440308) | Cod sursa (job #413681) | Cod sursa (job #413684)
Cod sursa(job #413684)
#include <stdio.h>
#include <stdlib.h>
void dinamic(int *a,int *best,int i,int n){
if (i==0) best[i]=1;
if (i==n) return;
int d=best[0];
int j;
for(j=0;j<i;j++)
if (a[i]>a[j])
if (best[j]>d)
d=best[j];
for( j=0;j<i;j++)
if (a[i]>a[j])
best[i]=1+d;
dinamic(a,best,++i,n);
}
int rec(int *a,int *best,int *s,int n){
int max=best[n-1];
int k=0;
for(int i = n-1;i>=0;i--)
if(best[i]>max)
max=best[i];
int j=n-1;
while(max>=1){
if (best[j]==max) {
s[k++]=a[j];
--max;
}
j--;
}
return k;
}
int main() {
int a[100000],best[100000];
int n;
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &n);
for (int i=0;i<n;i++)
scanf("%d", &a[i]);
for (int i=0;i<n;i++)
best[i]=1;
dinamic(a,best,0,n);
int k;
int s[n];
k=rec(a,best,s,n);
printf("%d \n",k);
for(int i=k-1;i>=0;i--)
printf("%d ",s[i]);
return 0;
}