Cod sursa(job #1112009)

Utilizator raluca1234Tudor Raluca raluca1234 Data 19 februarie 2014 12:36:00
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
//Subsir crescator maximal
#include<iostream>
#include<fstream>
using namespace std;

int main()
{
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    long n,i,j,maxlg,pozm,nr;
    long long a[100001],pozd[100001],lg[100001];
    f>>n;
    for ( i=1; i<=n; i++)
        f>>a[i];
    lg[n]=1;
    pozd[n]=0;
    maxlg=0;
    for ( i=n-1; i>=1; i--) {
        for (j=i+1; j<=n; j++)
            //caut maximul din lg[j]
            if (lg[j]>maxlg)
                if (a[j]>a[i]){
                    maxlg=lg[j];
                    pozm=j;
                    }
        //pun valorile
        lg[i]=maxlg+1;
        pozd[i]=pozm;
    }
    //Aflu lungimea maxima
    maxlg=0;
    for (i=1; i<=n; i++)
        if (maxlg<lg[i]){
            maxlg=lg[i];
            pozm=i;
            }
    g<<pozm<<'\n';
    nr=0;
    i=pozm;
    while (nr<maxlg)
    {
        g<<a[i]<<" ";
        i=pozd[i];
        nr++;
    }


    f.close();
    g.close();
    return 0;
}