Cod sursa(job #2133502)

Utilizator andr3i_kaabAndrei Ciineanu andr3i_kaab Data 17 februarie 2018 00:46:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
//#include <iostream>
#include <fstream>
/// este problema ciorii dinamice doar ca fara d dist
using namespace std;

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

int n, a[100005], viz[100005], best[100005], lmax, k, poz;

int main()
{
    int i, j;
    f>>n;
    for (i=1; i<=n; i++) f>>a[i];

    best[n]=1; viz[n]=-1;
    lmax=1; poz=n;
    for (i=n-1; i>=1; i--)
    {
        best[i]=1;
        viz[i]=-1;
        for (j=i+1; j<=n; j++)
          if (a[i]<a[j] && best[i]<best[j]+1)
          {
              best[i]=best[j]+1;
              viz[i]=j;
              if (best[i]>lmax)
              {
                  lmax=best[i];
                  poz=i;
              }
          }
    }

    cout<<lmax<<"\n";

    while (poz!=-1)
    {
        cout<<a[poz]<<" ";
        poz=viz[poz];
    }
    return 0;
}