Cod sursa(job #2354958)

Utilizator casuneanu.stefanstefan casuneanu casuneanu.stefan Data 25 februarie 2019 18:27:58
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n, i, lg[100010], urm[100010], a[100010], maxi, mx, j, nr;
int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>a[i];
        lg[i]=1;
    }
    for (i=n-1; i>=1; i--)
    {
        mx=1;
        for (j=i+1; j<=n; j++)
            if (a[i]<a[j] && 1+lg[j]>mx)
            {
                mx=1+lg[j];
                urm[i]=j;
            }
        lg[i]=mx;
        if (lg[i]>maxi)
            maxi=lg[i];
    }
    fout<<maxi<<'\n';
    for (i=1; 1; i++)
        if (lg[i]==maxi)
            break;
    fout<<a[i]<<' ';
    nr=1;
    while (1)
    {
        fout<<a[urm[i]]<<' ';
        i=urm[i];
        nr++;
        if (nr==maxi)
            break;
    }
    return 0;
}