Cod sursa(job #2176192)

Utilizator baragan30Baragan Andrei baragan30 Data 16 martie 2018 21:28:08
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
#define NMAX 100010
using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");
int v[NMAX],T[NMAX],L[NMAX];
int n,t;
void citire()
{
    f>>n;
    for(int i=1;i<=n;i++)f>>v[i];
}
void sir(int x){
for(int i=x-1;i>=1;i--)
{
    if(T[i]==0&&v[i]<v[x]){
        L[i]=L[x]+1;
        T[i]=x;
        sir(i);
    }
}
}
void dinamica()
{
    for(int i=n;i>=1;i--)
    {
        if(T[i]==0){L[i]=1;sir(i);}
    }
}
void cauta()
{
    int m1=0,m2;
    for(int i=1;i<=n;i++)
    {
        if(m1<L[i]){
            m1=L[i];
            m2=i;
        }
        if(m1>n-i)break;
    }
    t=m2;
}
void afisare(int x){
g<<x<<" ";
if(T[x]!=0)afisare(T[x]);
}
int main()
{
    citire();
    dinamica();
    cauta();
    g<<L[t]<<'\n';
    afisare(t);
}