Cod sursa(job #1012949)

Utilizator andreeaghetuUNIBUC andreeaghetu andreeaghetu Data 19 octombrie 2013 22:40:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
int N, a[100005], s[100005], poz_ant[100005];
ifstream in ("scmax.in");
ofstream out ("scmax.out");
void afisare_inv (int i)
{
    if (poz_ant[i]<0)
        out<<a[i]<<" ";
    else
    {
        afisare_inv(poz_ant[i]);
        out<<a[i]<<" ";
    }
}
int main()
{
    int max, max2, poz_max;
    in>>N;
    in>>a[0];
    s[0]=1;
    max2=1;
    poz_ant[0]=-1;
    for (int i=1;i<N;i++)
    {
        in>>a[i];
        max=0;
        poz_ant[i]=-1;
        for (int j=0;j<i;j++)
            if (a[j]<a[i] && s[j]>max)
                {
                    max=s[j];
                    poz_ant[i]=j;
                }
        s[i]=max+1;
        if (s[i]>max2)
        {
            max2=s[i];
            poz_max=i;
        }
    }
    out<<max2<<'\n';
    afisare_inv(poz_max);
    return 0;
}