Cod sursa(job #2336574)

Utilizator MrRaresRares Burghelea MrRares Data 5 februarie 2019 11:45:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

int v[1000005], d[1000005], cnt, p[1000005], vect[1000005];

int main()
{
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>v[i];
    }
    d[1]=1;
    for(int i=2; i<=n; ++i)
    {
        int maxim=0,prev;
        for(int j=i-1; j>=1; --j)
        {
            if(v[i]>v[j]){
                if(maxim<d[j]){
                    maxim=d[j];
                    prev=j;
                }
            }
        }
        d[i]=maxim+1;
        p[i]=prev;
    }
    int maxx=-1;
    int k=-1;
    for(int i=1; i<=n; ++i)
        if(d[i]>maxx){
            maxx=d[i];
            k=i;
        }
    cout<<maxx<<"\n";
    for(int i=1;i<=maxx;i++){
        vect[i]=v[k];
        k=p[k];
    }
    for(int i=maxx; i>=1; --i)
        cout<<vect[i]<<" ";
    return 0;
}