Cod sursa(job #1244769)

Utilizator flamey19Savu Daniel flamey19 Data 18 octombrie 2014 09:12:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,a[100010],L[100010],Max,x;

int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
    }
    L[n]=1;
    for(int i=n-1;i>=1;i--)
    {
        Max=0;

        for(int j=i+1;j<=n;j++)
        {
            if(Max<L[j] && a[j]>a[i]) Max=L[j];
        }
        L[i]=Max+1;
    }
    Max=0;
    int val=0;;
    for(int i=n;i>=1;i--)
    {
        if(L[i]>Max) {Max=L[i]; x=i; val++;}
    }
    g<<val<<endl;
    g<<a[x]<<" ";int u=a[x]; Max--;
    for(int i=x+1;i<=n;i++)
        if(L[i]==Max && u<a[i])
        {
                    g<<a[i]<<" ";
                    Max--;
                    u=a[i];

        }

    return 0;
}