Cod sursa(job #1529847)

Utilizator MithrilBratu Andrei Mithril Data 21 noiembrie 2015 11:27:56
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#define lng 100000
#include <stack>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[lng];
int b[lng]={0};
stack <int> S;
int main()
{
    int n;
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>a[i];
    int max1;
    b[0]=1;
    for(int i=0;i<n;i++)
    {
        max1=1;
        for(int j=i-1;j>0;j--)
        {
            if(a[j]<a[i])
            {
                if(b[j] + 1 >max1)
                {
                    max1=b[j] + 1;
                }
            }
        }
        b[i]=max1;
    }
    int copmax=max1;
    for(int i=n-1;i>=0;i--)
        if(b[i]==copmax)
        {
            S.push(a[i]);
            copmax--;
        }

    fout<<max1<<"\n";
    while(S.size())
    {
        fout<<S.top()<<" ";
        S.pop();
    }
    fin.close();
    fout.close();
    return 0;
}