Cod sursa(job #2479673)

Utilizator cyg_contnr1Rares Burghelea cyg_contnr1 Data 24 octombrie 2019 10:42:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>b;--i)
#define ll long long
#define codechef FAST int t;cin>>t;while(t--)
const int MAX=200000000;
const int MOD=9973;
int sp[1005][1005],dp[1005];
using namespace std;
int v[1000005], d[1000005], cnt, p[1000005], vect[1000005];
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    ll n;
    scanf("%lld",&n);
    f(i,1,n+1){
        scanf("%lld",&v[i]);
    }
    d[1]=1;
     f(i,2,n+1){
        ll maxim=0,prev;
        fd(j,i-1,0){
            if(v[i]>v[j]){
                if(maxim<d[j]){
                    maxim=d[j];
                    prev=j;
                }
            }
        }
        d[i]=maxim+1;
        p[i]=prev;
    }
    ll maxx=-1;
    ll k=-1;
    f(i,1,n+1){
        if(d[i]>maxx){
            maxx=d[i];
            k=i;
        }
    }
    printf("%lld\n",maxx);
    f(i,1,maxx+1){
        vect[i]=v[k];
        k=p[k];
    }
    fd(i,maxx,0){
        printf("%lld ",vect[i]);
    }
    return 0;
}