Cod sursa(job #1109517)

Utilizator DobosDobos Paul Dobos Data 17 februarie 2014 11:46:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int l[100000],urm[100000];

int main()
{
  int n,i,mx=0,pm=0,j,ok,p;
  f>>n;
  int v[n+1];
  l[n]=1;
  for(i=1;i<=n;i++)
    f>>v[i];

  for(i=n-1;i>=1;i--)
  {   l[i]=1;
      mx=0;
      pm=0;
      for(j=i+1;j<=n;j++)

          if(v[i]<v[j] && l[j]>mx)
  {
        mx=l[j];
        pm=j;
  }
l[i]=l[i]+mx;
urm[i]=pm;
  }
  mx=0;
  pm=0;
  for(i=1;i<=n;i++)
    if(l[i]>mx)
  {
      mx=l[i];
      pm=i;
  }

  g<<mx<<"\n";

  p=pm;
  while(p!=0)
  {
      g<<v[p]<<" ";
      p=urm[p];
  }
    return 0;
}