Cod sursa(job #1349708)

Utilizator EberardoVladianu Cosmin Eberardo Data 20 februarie 2015 13:43:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,a[100001],b[100001],t[100001];
void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];

}
void afis(int x)
{
    if(x==0) return;
    afis(t[x]);
    fout<<a[x]<<" ";
}

void caut(int j)
{
    int i;
    int poz=0;
    int maxim=0;
    for(i=j-1;i>=1;i--)
        if(a[i]<a[j])
            if(b[i]>maxim)
                {
                    maxim=b[i];
                    poz=i;
                }
    b[j]=maxim+1;
    t[j]=poz;
}
void rez()
{
    int i;
    int maxim=0;
    int poz=0;
    for(i=1;i<=n;i++)
        {
            caut(i);
            if(b[i]>maxim)
            {
                maxim=b[i];
                poz=i;
            }
        }
    fout<<maxim<<endl;
    afis(poz);
}
int main()
{
    citire();
    rez();

    return 0;
}