Pagini recente » Cod sursa (job #2281430) | Cod sursa (job #2046270) | Cod sursa (job #532993) | Cod sursa (job #1604515) | Cod sursa (job #66168)
Cod sursa(job #66168)
#include <stdio.h>
#define NMAX 5005
long int a[NMAX],v[NMAX],s[NMAX],sol[NMAX],TT[NMAX];
long int n,i,j,k;
void citire()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld",&a[i]);
}
void solve()
{
long int max;
max=a[n];s[n]=1;
long int st[NMAX];
for (i=n-1;i>=1;i--)
if (a[i]>max) {s[i]=1;max=a[i];}
else s[i]=0;
long int min;
min=a[1];
for (i=2;i<=n;i++)
if (a[i]<min) {st[i]=1;min=a[i];} else st[i]=0;
v[1]=1;TT[i]=0;
for (i=2;i<=n;i++)
{
max=-100000000;
v[i]=10005;
if (st[i]==1) {TT[i]=0;v[i]=1;}
for (j=i-1;j>=1;j--)
{
if (a[j]>a[i]) continue;
if (a[j]<=max) continue;
if (v[j]<v[i]-1) {v[i]=v[j]+1;TT[i]=j;max=a[j];continue;}
}
}
max=0;
long int x;
long int sol2[NMAX],ok=0;
max=100005;
for (i=1;i<=n;i++)
if ((s[i])&&(v[i]<max)) max=v[i];
for (i=1;i<=n;i++)
if ((s[i])&&(v[i]==max)){x=i;
k=0;
for (;x>0;x=TT[x])
sol2[++k]=x;
if (ok==0) {for (k=1;k<=max;k++) sol[k]=sol2[k];ok=1;continue;}
for (k=max;(sol[k]==sol2[k])&&(k>0);k--);
if (k&&(a[sol2[k]]<a[sol[k]])) for (k=1;k<=max;k++) sol[k]=sol2[k];
}
k=0;
printf("%ld\n",max);
for (i=max;i>=1;i--)
printf("%ld ",sol[i]);
}
int main()
{
citire();
solve();
return 0;
}