Cod sursa(job #1656302)

Utilizator mateibanuBanu Matei Costin mateibanu Data 19 martie 2016 09:29:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include<algorithm>

using namespace std;

FILE*f=fopen("scmax.in","r");
FILE*g=fopen("scmax.out","w");

int k,a[100001],mx,n,l[100001];

void solve()
{
    int i,j;
    l[n]=1;
    for (i=n-1;i>=1;i--)
    {
        mx=0;
        for (j=i+1;j<=n;j++)
            if (l[j]>mx&&a[i]<a[j]) {mx=l[j];}
        l[i]=mx+1;
    }
    mx=l[1];
    k=1;
    for (i=2;i<=n;i++) if (mx<l[i]) {mx=l[i];k=i;}
}

void afis()
{
    int i;
    fprintf(g,"%d\n",mx);
    for (i=k;i<=n&&mx;i++)
        if (l[i]==mx)
    {
        fprintf(g,"%d ",a[i]);
        mx--;
    }
}
int main()
{
    int i;
    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
    solve();
    afis();
    fclose(g);
    fclose(f);
    return 0;
}