Cod sursa(job #2295857)

Utilizator stefandDragoi Stefan stefand Data 3 decembrie 2018 23:38:07
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long long v[100005],i,maxi,lgmax[100005],n,succ[100005],lmaxi,p,pmax,j;
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
    lgmax[n]=1;
    lmaxi=1;
    for(i=n-1; i>0; i--)
    {
        maxi=0;
        p=i;
        for(j=i+1; j<=n; j++)
            if(maxi<lgmax[j] && v[i]<v[j])
                maxi=lgmax[j], p=j;
        lgmax[i]=1+maxi;
        succ[i]=p;
        if(lgmax[i]>lmaxi) lmaxi=lgmax[i], pmax=i;
    }
    fout<<lmaxi<<"\n";
    while(pmax!=succ[pmax])
        fout<<v[pmax]<<" ", pmax=succ[pmax];
    return 0;
}