Cod sursa(job #1350091)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 20 februarie 2015 17:38:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
ofstream g("scmax.out");
int a[100001],b[100001],c[100001],maxim,i,j,n,t;
int main()
{
    freopen("scmax.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=1;
    }
    for(i=n-1;i>=1;i--)
    {
        for(j=n;j>=i+1;j--)
        {
            if(a[i]<a[j])
            {
                if(b[j]+1>b[i])
                {
                    b[i]=b[j]+1;
                    c[i]=j;
                }
            }
        }
    }
    maxim=0;
    for(i=1;i<=n;i++)
    {
        if(b[i]>maxim)
        {
            maxim=b[i];
            t=i;
        }
    }
    g<<maxim<<'\n';
    g<<a[t]<<" ";
    while(c[t]!=0)
    {
        g<<a[c[t]]<<" ";
        t=c[t];
    }
    return 0;
}