Cod sursa(job #825367)

Utilizator ctraulChicinas T. Raul ctraul Data 28 noiembrie 2012 21:55:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
using namespace std;
#define maxx 100000
#include <iostream>
#include <fstream>
int DP[maxx],x[maxx],mx,sm,n,smpoz;
int main()
{
  ofstream fout("scmax.out");
  ifstream fin("scmax.in");

  fin>>n;
  for (int i=1;i<=n;i++)
    {
      fin>>x[i];
    }

  for (int i=n;i>=1;i--)
    {
      mx=0;
      for (int j=i+1;j<=n;j++)
        {
          if ((x[j]>x[i])&&(DP[j]>mx))
            mx=DP[j];
        }
      DP[i]=mx+1;
      if (sm<DP[i])
        {
          sm=DP[i];
          smpoz=i;
        }
    }

  fout<<DP[smpoz]<<'\n'<<x[smpoz]<<' ';
  for (int i=smpoz+1;i<=n;i++)
    if (x[smpoz]<x[i]&&DP[i]==sm-1)
      {
        fout<<x[i]<<' ';
        sm--;
      }
}