Cod sursa(job #1873280)

Utilizator ionutz28Ionut Constantinescu ionutz28 Data 8 februarie 2017 21:42:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <stdio.h>
using namespace std;
FILE *in,*out;
int i,j,n,maxi,pmax;
int v[100001],d[100001],a[100001],k,u;
int lung(int n)
{
    if(n==1)
        return(d[1]=1);
    else
    {
        lung(n-1);
        int best=0;
        int j=n-1;
        while(j)
        {
            if(v[j]<v[n])
            {
                if(d[j]>best)
                    best=d[j];
            }
            j--;
        }
        best++;
        if(best>maxi)
          {
             maxi=best;
             pmax=n;
          }
        return(d[n]=best);
    }
}
int main()
{
    in=fopen("scmax.in","r");
    out=fopen("scmax.out","w");
    fscanf(in,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);
    lung(n);
    fprintf(out,"%d\n",maxi);
    u=pmax;
    a[++k]=v[pmax];
    for(j=pmax-1;j>0;j--)
    {
        if(d[j]==d[u]-1)
        {
            if(v[j]<v[u]){
                a[++k]=v[j];
                u=j;
            }
        }
    }
    for(i=k;i>0;i--)
        fprintf(out,"%d ",a[i]);



    return 0;
}