Cod sursa(job #1260170)

Utilizator andreip1996Paun Andrei andreip1996 Data 10 noiembrie 2014 22:43:15
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
//subsir crescator maximal al unui sir

#include <stdio.h>

int a[100],lg[100],poz[100];

int main()
{
    int n,i,p,max,maxlg,pozmax;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=0;i<n;i++)
       {
           scanf("%d",&a[i]);
       }
    lg[n-1]=1;
    poz[n-1]=-1;

    for(i=n-2;i>=0;i--)
    {
        max=0;p=i;
        for(int j=i+1;j<n;j++)
           if(lg[j]>max && a[i]<a[j])
           {
               max=lg[j];
               p=j;
           }
        lg[i]=max+1;
        poz[i]=p;
    }

    maxlg=lg[0];
    pozmax=0;
    for(i=1;i<n;i++)
       if(lg[i]>maxlg)
            maxlg=lg[i],pozmax=i;
    printf("%d\n",maxlg);
    i=pozmax;
    while(i!=-1)
      {
          printf("%d ",a[i]);
          i=poz[i];
      }
    return 0;
}