Cod sursa(job #305416)

Utilizator robigiirimias robert robigi Data 17 aprilie 2009 10:20:22
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
using namespace std;

ifstream f ("scmax.in");
ofstream g ("scmax.out");

int n, w[100001], t[100001], tt[100001];
long long v[100001];

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

void program()
{    for (int i=1; i<=n; i++)
         for (int j=1; j<i; j++)
             if (v[i]>v[j]) { w[i]=w[j]+1; t[i]=j; }
     int max=0;
     int h;
     for (int k=1; k<=n; k++)
         if (w[k]>max) { max=w[k]; h=k; }
     g << max+1 << "\n";
     int o=1;
     while (h!=0)
     {      tt[o++]=v[h];
            h=t[h];
     }
     for (int m=o-1; m>=1; m--)
          g << tt[m] << " ";
} 

int main()
{   read();
    program();
    return 0;
}