Cod sursa(job #1369394)

Utilizator bianncaPoenar Bianca biannca Data 3 martie 2015 00:28:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include<fstream>
#define m 100000
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[m],best[m],poz[m],n,i,k,pozi,mx,mmax=0;
int main()
{
    int i,j;
    fin>>n;
    best[n]=1;//lung max a subsir cresc care se termina pana la n
    poz[n]=-1;//pozitia valorii care preceda elem  n in scmax care se termina la n
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    for(i=n-1;i>0;i--)
    {
        best[i]=1;
        poz[i]=-1;
        for(j=i+1;j<=n;j++)
            if(a[j]>a[i] &&best[j]+1>best[i])
        {
            best[i]=best[j]+1;
            poz[i]=j;
            if(best[i]>mmax){mmax=best[i]; pozi=i;}
        }
    }
    fout<<mmax<<'\n';
    i=pozi;
    while(i!=-1)
    {
        fout<<a[i]<<" ";
        i=poz[i];
    }
    return 0;
}