Cod sursa(job #1218163)

Utilizator rangerChihai Mihai ranger Data 9 august 2014 19:09:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");
const int nmax = 100010;
int n,a[nmax],best[nmax],pre[nmax],sol[nmax],i,j,bst,poz,k=0;

int main()
{
    cin>>n;
    for (i=1;i<=n;i++) cin>>a[i];
    for (i=1;i<=n;i++) best[i]=1;
    for (i=2;i<=n;i++){
        for (j=1;j<=i-1;j++)
          if (a[j]<a[i])
           {
               if (best[j]+1>best[i])
                best[i]=best[j]+1,
                pre[i]=j;
           }
        if (best[i]>bst)
            bst=best[i],
            poz=i;
    }
    cout<<bst<<"\n";
    for (;poz;poz=pre[poz]) sol[++k]=a[poz];
    for (i=k;i>0;i--) cout<<sol[i]<<" ";
    return 0;
}