Cod sursa(job #1662624)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 24 martie 2016 22:17:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

stack <int> x;

int a[100002];
int b[100002];
int poz[100002];

int maxim=-1;
int pmax;

int main()
{
    int n;

    fin >> n;

    for(int i=1; i<=n; i++)
        b[i]=1;

    for(int i=1; i<=n; i++)
    {
        fin >> a[i];

        bool sem=false;

        for(int j=i-1; j>=1; j--)
        {
            if(a[i]>a[j])
            {
                if((b[j]+1)>b[i] && sem==true)
                {
                    b[i]=b[j]+1;
                    poz[i]=j;
                }


                if(sem==false)
                {
                    b[i]=b[j]+1;
                    sem=true;
                    poz[i]=j;
                }

                if(b[i]>maxim)
                {
                    maxim=b[i];
                    pmax=i;
                }
            }
        }
    }

    fout << maxim << '\n';

    int pct=pmax;

    while(b[pct]!=1)
    {
        x.push(a[pct]);

        pct=poz[pct];
    }

    x.push(a[pct]);

    while(!x.empty())
    {
        fout << x.top() << " ";
        x.pop();
    }




    return 0;
}