Cod sursa(job #1570507)

Utilizator andreiudilaUdila Andrei andreiudila Data 16 ianuarie 2016 16:25:35
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 a[100001],i,dp[100001],n,j,sol[100001],k;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];

        dp[1]=1;
        for(i=2;i<=n;i++)
        {   dp[i]=1;
            for(j=i-1;j>=1;j--)
                if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
        }

        int maxi=0,pmax=0;

        for(i=1;i<=n;i++)
            if(dp[i]>maxi) maxi=dp[i],pmax=i;

              fout<<maxi<<'\n';

        sol[++k]=a[pmax];

        for(i=pmax-1;i>=1;--i)
        {
            if(dp[pmax]==dp[i]+1 && a[i]<a[pmax]) { sol[++k]=a[i]; pmax=i;}
        }


        for(i=k;i>=1;--i)
            fout<<sol[i]<<" ";
    return 0;
}