Cod sursa(job #2590325)

Utilizator Davla2Stancu Vlad Davla2 Data 27 martie 2020 19:10:32
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <iostream>

using namespace std;

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

const int N=100000;

int v[N+1],lung[N+1],pred[N+1],sir[N+1];

int main()
{
    int n,maxp=0,cnt=0;
    in>>n;
    for(int i=0; i<n; i++)
    {
        in>>v[i];
        pred[i]=-1;
    }
    for(int i=0; i<n; i++)
    {
        lung[i]=0;
        for(int j=0; j<i; j++)
        {
            if(v[j]<v[i])
            {
                if(lung[j]>lung[i])
                {
                    lung[i]=lung[j];
                    pred[i]=j;
                }
            }
        }
        lung[i]++;
        //cout<<lung[i]<<" ";
        if(lung[i]>lung[maxp]) maxp=i;
    }
    out<<lung[maxp]<<"\n";
    while(maxp>-1)
    {
        sir[cnt++]=v[maxp];
        maxp=pred[maxp];
    }
    for(int i=cnt-1; i>=0; i--) out<<sir[i]<<" ";
    return 0;
}