Cod sursa(job #2853361)

Utilizator barbu_adrianBarbu Costin-Adrian barbu_adrian Data 20 februarie 2022 10:53:55
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>

using namespace std;

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

int main()
{
    /*
    int n, i, j, poz, lg=1, lmax=0,  var, max[1001], aux[1001], v[1001];
    cin>>n;
    for (i=1; i<=n; i++)
        cin>>v[i];
    for (i=1; i<=n; i++)
    {
        aux[1]=v[i], poz=2;
        lg=1, var=v[i];
        for (j=i+1; j<=n; j++)
            if (v[j]>var)
            {
                lg++;
                aux[poz++]=v[j];
                var=v[j];
            }
        if (lg>lmax)
           {
               lmax=lg;
               for (j=1; j<=lmax; j++)
                    max[j]=aux[j];
           }
    }
    for (i=1; i<=lmax; i++)
        cout<<max[i]<<' ';
    return 0;
    */

    int v[1001], lung[1001], poz[1001], pozm;
    int n,l, lmax=0,i ,j ;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i];
    lung[n]=1;
    for(i=n; i>=1 ;i--){
        int p=i, l=0;
        for(j=i+1 ; j<=n; j++)
            if(v[j]>=v[i] && lung[j]>l){
                p=j;
                l=lung[j];
        }
        lung[i]=l+1;
        poz[i]=p;
        if(lung[i]>lmax)
        {
            lmax=lung[i];
            pozm=i;
        }
    }
    i=pozm;
    while(lmax--)
    {
        cout<<v[i]<<' ';
        i=poz[i];
    }
    return 0;
}