Cod sursa(job #2613452)

Utilizator teodora019Nae Teodora Ioana teodora019 Data 9 mai 2020 19:53:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;

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

int a[100001], d[100001], re[100001];

int main() {

    int n, i, j, maxx, p;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i];
    d[n]=1;
    re[n]=-1;
    maxx=1;
    p=n;
    for (i=n-1; i>0; i--)
        {d[i]=1;
        re[i]=-1;
        for(j=i+1; j<=n; j++)
            {
            if(d[j]+1>d[i] && a[j] > a[i])
            {d[i]=d[j]+1;
            re[i]=j;
            }
            if (d[i]>maxx) {

                maxx=d[i];
                p=i;
            }
        }
    }

    cout<<maxx<< '\n';
    i=p;
    while (i!=-1)
        {
        cout<<a[i]<<' ';
        i=re[i];
    }

    return 0;

}