Cod sursa(job #2093226)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 23 decembrie 2017 11:29:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;
int max2;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long long a[100000];
int p[100001],d[100001],i,j,maxx,poz;
int n;
void citire(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>a[i];
}
void afisare(int k)
{
    fout<<p[max2]<<"\n";
    while(k>0)
    {
        fout<<a[k]<<" ";
        k=d[k];
    }
}
void sel(){
p[n]=1;
d[n]=0;
for(i=n-1;i>=1;i--)
{
    maxx=0;
    poz=0;
    for(j=i+1;j<=n;j++)
        if(a[j]>a[i]&&maxx<p[j])
        {
            maxx=p[j];
            poz=j;
        }
     p[i]=maxx+1;
     d[i]=poz;
 if(p[max2]<p[i])
    max2=i;
}
afisare(max2);
}
int main()
{
citire();
sel();
}