Cod sursa(job #2296949)

Utilizator Victor_IonescuVictor Ionescu Victor_Ionescu Data 5 decembrie 2018 09:29:23
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
int v[5001],l[5001],pred[5001],imax,n;

void dinamica()
{
    l[1]=imax=1;
    for (int i=2;i<=n;i++)
      {
        l[i]=1;
        for (int j=1;j<=i-1;j++)
            if (v[i]>=v[j] && (l[j]+1>l[i] || l[i]==l[j]+1 && v[j]<v[pred[i]]))
                l[i]=l[j]+1, pred[i]=j;
        if (l[imax]<l[i] || l[imax]==l[i] && v[imax]>v[i]) imax=i;
      }
}

void afisare(int i)
{
    if (i!=0)
        afisare(pred[i]),cout<<i<<' ';
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>v[i];
    dinamica();
    cout<<l[imax]<<'\n';
    afisare(imax);
    return 0;
}