Cod sursa(job #1918011)

Utilizator ianiIani Biro iani Data 9 martie 2017 13:53:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin ("scmax.in");
    ofstream fout ("scmax.out");
    int n,a[100001],fr[100001],maxiout=-1;
    fin>>n;
    fr[n-1]=1;
    for (int i=0; i<n; i++)
        fin>>a[i];
    for (int i=n-1; i>=0; i--)
    {
        int maxi=-1;
        for (int j=i+1; j<n; j++)
            if (a[j]>a[i]&&fr[j]>maxi)
                maxi=fr[j];
        if (maxi!=-1)
            fr[i]+=maxi+1;
        else
            fr[i]=1;
        if (fr[i]>maxiout)
            maxiout=fr[i];
    }
    fout<<maxiout<<'\n';
    int ant=-1;
    for (int i=0; i<n; i++)
    {
        if (fr[i]==maxiout&&a[i]>ant)
        {
            fout<<a[i]<<' ';
            maxiout--;
            ant=a[i];
        }
    }
    return 0;
}