Cod sursa(job #2530949)

Utilizator pimao2004Lupu Stefan Dragos pimao2004 Data 25 ianuarie 2020 15:06:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;
ifstream in ("scmax.in");
ofstream out ("scmax.out");
int sir[100137];
int nextt[100137];
int v[100137];
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
    }
    sir[n]=1;
    int maxi=1,start=n;
    for(int i=n-1;i;i--)
    {
        sir[i]=1;
        for(int j=i+1;j<=n;j++)
        {
            if(v[i]<v[j]&&sir[i]<sir[j]+1)
            {
                sir[i]=sir[j]+1;
                nextt[i]=j;
                if(sir[i]>maxi)
                {
                    maxi=sir[i];
                    start=i;
                }
            }
        }
    }
    out<<maxi<<'\n';
    while(start)
    {
        out<<v[start]<<' ';
        start=nextt[start];
    }
    return 0;
}