Cod sursa(job #1124983)

Utilizator varononoVaro Norbert varonono Data 26 februarie 2014 14:57:33
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>

using namespace std;

int a[100000],best[1000],poz[100],p,n,max ,sol;

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
}
void dinamic()
{
    int i,j;
    best[n]=1;
    poz[n]=-1;
    max=1;
    p=n;
    for(int i=n-1;i>=1;i--)
    {
        best[i]=1;
        poz[i]=-1;
   for(j=i+1;j<=n;++j)
       if(a[i]<a[j] && best[i]<best[j]+1)
         {
         best[i]=best[j]+1;
         poz[i]=j;
         if(best[i]>max) max=best[i],p=i;
         }
        }
    }
void contr()
{
    int i;i=p;
    while(i!=-1)
    {
         printf("%d ",a[i]);
         i=poz[i];
    }
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    read();
    dinamic();
    printf("%d\n",max);
    contr();

}