Cod sursa(job #2703269)

Utilizator AndreiStreheStreche Andrei Claudiu AndreiStrehe Data 7 februarie 2021 21:43:01
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,i,max1,pozitia,j;
int nr[100005],pozitiemax[100005],pozitiecautata[100005];

void calc()
{
    pozitiemax[n]=1;
    pozitiecautata[n]=-1;
    max1=0;

    for(i=n-1;i>=1;i--)
    {
        pozitiemax[i]=1;
        pozitiecautata[i]=-1;
        for(j=i+1;j<=n;j++)
        {
            if(pozitiemax[j]+1>pozitiemax[i] && nr[j]>nr[i])
            {
                pozitiemax[i]=pozitiemax[j]+1;
                pozitiecautata[i]=j;
                if(pozitiemax[i]>max1)
                {
                    max1=pozitiemax[i];
                    pozitia=i;
                }

            }
        }
    }
}

int main()
{
    f>>n;

    for(i=1;i<=n;i++)
    {
        f>>nr[i];
    }

    calc();

    g<<max1<<'\n';

    while(pozitia!=-1)
    {
        g<<nr[pozitia]<<" ";
        pozitia=pozitiecautata[pozitia];
    }

    return 0;
}