Cod sursa(job #1103399)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 9 februarie 2014 15:52:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
using namespace std;
const int MAXN=100005;
int n,SOL_MAX,POZ_MAX;
int a[MAXN],next_cell[MAXN],lis[MAXN];
void read()
{
    ifstream fin("scmax.in");
    fin>>n;
    for (int i=1; i<=n; lis[i]=1, ++i)
        fin>>a[i];
    fin.close();
}
void write()
{
    ofstream fout("scmax.out");
    fout<<lis[POZ_MAX]<<'\n';
    for (int i=POZ_MAX; i!=0; i=next_cell[i])
        fout<<a[i]<<' ';
    fout.close();
}
void solve()
{
    int i,j;
    for (i=n-1; i>=1; --i)
    {
        for (j=i+1; j<=n; ++j)
        {
            if (1+lis[j]>lis[i] && a[j]>a[i])
            {
                lis[i]=1+lis[j];
                next_cell[i]=j;
            }
        }
        if (lis[i]>lis[POZ_MAX])
            POZ_MAX=i;
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}