Cod sursa(job #2291668)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 28 noiembrie 2018 14:46:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#define nl '\n'
using namespace std;

int n, a[100000],l[100000],urm[100000];

int main()

{

    int m=0;
    ios_base::sync_with_stdio(false);

    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    cin >> n;
    for(int i=0;i<n;++i)
        cin >> a[i];
        //scanf("%d",&a[i]);

    l[n]=1;

    urm[n]=-1;

    for(int i=n-1;i>=0;--i){

        l[i]=1;

        urm[i]=-1;

        for(int j=1+i;j<n;++j){

            if(l[j]+1>l[i]&&a[j]>a[i]){

                l[i]=l[j]+1;

                urm[i]=j;

            }

        }

        if(l[i]>l[m])
            m=i;
    }
    cout << l[m] << nl;
    for(int i=m;i!=-1;i=urm[i])
        cout << a[i] << ' ';
        //printf("%d ",a[i]);
    return 0;

}