Cod sursa(job #1049065)

Utilizator cosmin004Manolescu Cosmin cosmin004 Data 6 decembrie 2013 20:46:42
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fi("date.in");
ofstream fo("date.out");
int n, v[100],lg[100],urm[100], max_lg,cnt;

void citire()
{
    fi>>n;
    for (int i=1;i<=n;i++)
        fi>>v[i];
}

void generare()
{
    int poz_lg,m;
    lg[n]=1;
    urm[n]=0;
    for (int i=n-1;i>=1;i--)
    {
        m=0;
        poz_lg=i;
        for(int j=i+1;j<=n;j++)
            {
                if (v[i]<v[j]&&lg[j]>m)
                    {
                        m=lg[j];
                        poz_lg=j;
                    }
            }
            if (m==0) urm[i]=0;
            else urm[i]=poz_lg;
            lg[i]=m+1;
            max_lg=max(lg[i],max_lg);
    }
}
void aparitii()
{
    int k=0, ok=0;
    for (int i=1;i<=n;i++)
        {
            ok=0;
            if(lg[i]==max_lg)
                {
                    k=i;
                    ok=1;
                    while (k!=0)
                        {
                            cnt++;
                            k=urm[k];
                        }
                }

        }
}
void drum()
{
    int k=0, ok=0;
    for (int i=1;i<=n;i++)
        {
            ok=0;
            if(lg[i]==max_lg)
                {
                    k=i;
                    ok=1;
                    while (k!=0)
                        {
                            fo<<v[k]<<" ";
                            k=urm[k];
                        }
                }
            if(ok==1)
                fo<<'/n';
        }
}

int main()
{
    citire();
    generare();
    aparitii();
    fo<<cnt<<'/n';
    drum();
    return 0;

}