Cod sursa(job #2479698)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 24 octombrie 2019 11:36:10
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;

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

const int L = 16;
long long b,v[100005],n,k,d[100005],indi,maxi,a[100005];

int caut(int x,int sf)
{
    int in=1,r=0,mij;
    while(in<=sf){
        mij=(in+sf)/2;
        if(v[mij]<x){
            in=mij+1;
            r=mij;
        }
        else{
            sf=mij-1;
        }
    }
    return r;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        b=caut(v[i],i);
        if(b){
            if(v[i]==v[b]){
                d[i]--;
            }
            d[i]+=d[b]+1;
        }
        else{
            d[i]=1;
        }
        if(d[i]>maxi){
            maxi=d[i];
            indi=i;
        }
    }
    cout<<maxi<<'\n';
    long long maxi1=maxi;
    a[maxi]=v[indi];
    for(int i=indi-1;i>=0;i--){
        if(v[i]<v[indi] && d[i]==maxi-1){
            indi=i;
            maxi--;
            a[maxi]=v[i];
        }
    }
    for(int i=1;i<=maxi1;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}