Cod sursa(job #1969328)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 18 aprilie 2017 13:38:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[Nmax];
int t[Nmax];
int lg[Nmax];
int main()
{int n,i,j;
f>>n;
for(i=1;i<=n;i++)
f>>v[i];
lg[n]=1;
t[n]=0;
for(i=n-1;i>0;i--)
{
    int maxx=0,tata=0;
    for(j=i+1;j<=n;j++)
    if(v[j]>v[i])
    {
        if(lg[j]>maxx)
        {
            maxx=lg[j];
            tata=j;
        }
    }
    lg[i]=maxx+1;
    t[i]=tata;
}
int maxx=0,poz;
for(i=1;i<=n;i++)
{
    if(lg[i]>maxx)
    {
        maxx=lg[i];
        poz=i;
    }
}
g<<maxx<<'\n';
while(poz)
{
    g<<v[poz]<<' ';
    poz=t[poz];
}

    return 0;
}