Cod sursa(job #715415)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 17 martie 2012 10:35:13
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<stdio.h>

int a[5005],n;

void cel_mai_mic_scm(int a[], int n)
{
int b[5005], i, j, vmax, poz, lmax, p, x;

lmax=0;
for (i=n;i>=1;i--)
{
vmax=0;
for (j=i+1;j<=n;j++)
  if (a[i]<=a[j]  && b[j]>vmax) {vmax=b[j];}
b[i]=vmax+1;
if (b[i]>=lmax){lmax=b[i];poz=i;}
}

printf("%d\n",lmax);
for (i=1;i<=lmax;i++)
{
x=1000001;
p=poz;
for (j=poz;j<=n;j++)
  if (b[j]==lmax+1-i  &&  a[j]<x)
    {
    x=j;
    p=j;
    }
printf("%d ",x);
poz=p;
}
}
int main()
{
int i;
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
cel_mai_mic_scm(a,n);
fclose(stdin);
fclose(stdout);
return 0;
}