Cod sursa(job #2573728)

Utilizator dumitrustefania1DUMITRU STEFANIA dumitrustefania1 Data 5 martie 2020 18:54:09
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#include <cstring>
# define pb push_back
#define nmax 100002
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
string a,b;
int ok,k,i,n,best[nmax],j,max1,urm[nmax],p,poz,v[nmax],nr;

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];

    best[n]=1;
    for(i=n-1;i>=1;i--)
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j])
            {       if(best[i]<best[j]+1)
            {
                best[i]=best[j]+1;
                if(best[i]>max1)
                {
                    max1=best[i];
                    poz=i;
                }
                urm[i]=j;
            }

            }


//g<<best[poz]<<"\n";
p=poz;
    while(poz)
    {
        //g<<v[poz]<<" ";
        nr++;
        poz=urm[poz];
    }
g<<nr<<"\n";
poz=p;
 while(poz)
    {
        g<<v[poz]<<" ";

        poz=urm[poz];
    }
    return 0;
}