Mai intai trebuie sa te autentifici.
Cod sursa(job #361263)
Utilizator | Data | 4 noiembrie 2009 12:53:17 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.96 kb |
#include <stdio.h>
int a[100002],s1[100002],s2[100002];
int n,lg;
void citire()
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
}
void rezolvare()
{
int i,j;
bool ok;
for(i=1;i<=n;i++)
{
for(j=0,ok=false;!ok&&j<lg;j++)
{
if(s1[j]>a[i])
{
s1[j]=a[i];
s2[i]=j;
ok=true;
}
else if(s1[j]==a[i])ok=true;
}
if(!ok)
s1[lg]=a[i],s2[i]=lg++;
}
}
void afisare()
{
printf("%d\n",lg);
int k=0;
lg--;
while(lg>=0)
{
if(s2[n]==lg)
{
s1[++k]=a[n];
lg--;
}
n--;
}
while(k)
printf ("%d ",s1[k--]);
}
int main ()
{
freopen ("scmax.in","r",stdin);
freopen ("scmax.out","w",stdout);
scanf("%d",&n);
citire();
rezolvare();
afisare();
return 0;
}