Cod sursa(job #1473517)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 19 august 2015 15:48:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#define NMAX 100002
using namespace std;

int a[NMAX],l[NMAX],poz[NMAX],n,maxim,pozm;

int main()
{
    ifstream in("scmax.in");
    ofstream out("scmax.out");
    in >> n;
    for(int i=1;i<=n;i++)
        in >> a[i];
    l[n]=1;
    poz[n]=-1;
    for(int i=n-1;i>0;i--)
    {
        poz[i]=-1;
        l[i]=1;
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]<a[j] && l[i]< 1 + l[j])
            {
                l[i] = 1 + l[j];
                poz[i]= j;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(l[i]>maxim)
    {
        maxim = l[i];

        pozm = i;
    }
    out << maxim << "\n";
    while(pozm!=-1)
    {
        out << a[pozm] << " ";
       // cout << pozm << " ";
        pozm = poz[pozm];
    }

    return 0;
}