Cod sursa(job #1892721)

Utilizator radu.damianDamian Radu radu.damian Data 25 februarie 2017 11:12:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,i,a[100005],lgmax[100005];
void calcul()
{
    int k,i,maxi=1,ind=0,maxi1;
    lgmax[n]=1;
    for(k=n-1;k>=1;k--)
    {
        lgmax[k]=1;
        for(i=k+1;i<=n;i++)
            if(a[k]<a[i])
             lgmax[k]=max(lgmax[k],lgmax[i]+1);
        if(lgmax[k]>maxi)
           {
            maxi=lgmax[k];
            ind=k;
           }



    }
    maxi1=maxi;
    fout<<maxi<<'\n';
    i=ind;
    while(i<=n)
        {
        if(lgmax[i]==maxi1)
    {
        fout<<a[i]<<' ';
        maxi1--;
    }
    i++;
        }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];

    calcul();
    return 0;
}