Cod sursa(job #1860970)

Utilizator costinghibanGhiban Costin costinghiban Data 28 ianuarie 2017 15:06:48
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

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

const int N=100000;
int lmax,lung[N],pred[N],v[N],n;

void sir(int p){
    if(pred[p]!=0){
        sir(pred[p]);
    }
    out<<v[p]<<" ";
}

int main()
{
    in>>n;
    int i,j;
    for(i=0;i<n;i++)
        in>>v[i];

    for(i=1;i<=n;i++){
        lmax=0;
        for(j=1;j<i;j++){
            if(v[j]<v[i]){
                if(lung[j]>lmax){
                    lmax=lung[j];
                    pred[i]=j;
                }
            }
        }
        lung[i]=1+lmax;
    }
    int pmax=1;
    for(i=2;i<=n;i++){
        if(lung[i]>lung[pmax]){
            pmax=i;
        }
    }
    out<<lung[pmax]<<'\n';
    sir(pmax);
    return 0;
}