Cod sursa(job #1662654)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 24 martie 2016 22:41:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <stack>
#include <stdio.h>

using namespace std;

FILE *f(fopen("scmax.in", "r"));
FILE *g(fopen("scmax.out", "w"));

stack <int> x;

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

int maxim=-1;
int pmax;

int main()
{
    int n;

    fscanf(f, "%d", &n);

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

    for(int i=1; i<=n; i++)
    {
        fscanf(f, "%d", &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;
                }
            }
        }
    }

    fprintf(g, "%d\n", maxim);

    int pct=pmax;

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

        pct=poz[pct];
    }

    x.push(a[pct]);

    while(!x.empty())
    {
        int y;

        y=x.top();

        fprintf(g, "%d ", y);
        x.pop();
    }

    fclose(f);
    fclose(g);

    return 0;
}