Cod sursa(job #1120195)

Utilizator yoyoisitm Ionescu Andrei yoyois Data 24 februarie 2014 22:07:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;
int a[100003],maxi[100003],n, nexti[100003];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main()
{
    f>>n;
    for(int i=1; i<=n;i++)
        f>>a[i];

        maxi[n]=1;
        int it,l=0;
    for (int i=n; i>0;i--)
    {
        maxi[i]=1;
        nexti[i]=0;
        for(int j=i; j<=n;j++)
        {
            if(a[i]<a[j] && maxi[i]<=maxi[j])
            {
                maxi[i]=maxi[j]+1;
                nexti[i]=j;
            }
        }
        if(maxi[i]>l){l=maxi[i]; it=i;}
    }
    g<<l<<"\n";
    int start=it;
    for(int i=1; i<=l;i++){ g<<a[start]<<" "; start=nexti[start]; }
    return 0;
}