Cod sursa(job #1243799)

Utilizator delia_99Delia Draghici delia_99 Data 16 octombrie 2014 14:03:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,a[100005],nr[100005],x,Max,y,i,j;
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
      f>>a[i];
    nr[n]=1;
    for(i=n-1;i>=1;--i)
    {
        x=0;
        for(j=i+1;j<=n;++j)
          if(a[i]<a[j]&&nr[j]>x)
                x=nr[j];
        if(x>0)
        nr[i]=x+1;
        else nr[i]=1;
    }
    Max=0;
    for(i=1;i<=n;i++)
      if(nr[i]>Max)
      {
          Max=nr[i];
          y=i;
      }
    g<<Max<<'\n';
    g<<a[y]<<" ";
    Max--;
    while(Max>0)
    {
        for(i=y+1;i<=n;++i)
          if((nr[i]==Max)&&a[i]>a[y])
            {
                Max--;
                g<<a[i]<<" ";
                y=i;
                break;
            }
    }
    g<<'\n';


    return 0;
}