Cod sursa(job #2694042)

Utilizator asbiancaBianca Gabriela Asavoaei asbianca Data 7 ianuarie 2021 21:51:18
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, a[N];
int i, j;
int L[N], drum[N], k;

void Scmax()
{
    L[n]=1;
    drum[n]=n;
    for(i=n; i>=1; i--)
    {
        L[i]=1;
        drum[i]=1;
        for(j=i+1; j<=n; j++)
            if(a[i] < a[j] && L[i] <= L[j])
            {
                L[i]=L[j]+1;
                drum[i]=j;
            }
    }
    int mx=1;
    for(i=1; i<=n; i++)
        if(mx < L[i])
        {
            mx=L[i];
            k=i;
        }
}

void Afisare()
{
    fout << L[k] <<"\n";
    for(i=1, j=k; i<=L[k]; i++,  j=drum[j])
        fout << a[j] <<" ";
}
int main()
{
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> a[i];
    Scmax();
    Afisare();

    return 0;
}