Cod sursa(job #2300613)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 11 decembrie 2018 20:25:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n;
struct Best
{
    int val,best,urm;
    Best()
    {
        best=1;
        urm=0;
    }
};
Best x[100001];


int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>x[i].val;

    int pmax=0;
    x[0].best=0;
    for(int i=n-1;i>=1;i--)
    {   int cmax=0;
        for(int j=n;j>i;j--)
            if(x[j].best>x[cmax].best && x[j].val>x[i].val)
                cmax=j;
        x[i].best=1+x[cmax].best;
        x[i].urm=cmax;
        if(x[pmax].best<x[i].best)
            pmax=i;
    }
    g<<x[pmax].best<<endl;
    while(x[pmax].best)
    {
        g<<x[pmax].val<<' ';
        pmax=x[pmax].urm;
    }

    return 0;
}