Cod sursa(job #3315055)

Utilizator zionlyismAdobroaiei David zionlyism Data 12 octombrie 2025 09:24:17
Problema Subsir crescator maximal Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#define NMAX 1002
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n;
int a[NMAX];
int lgmax[NMAX], urm[NMAX];
int i, j, maxim, pozurm, pozmax;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    //initializare
    lgmax[n]=1; urm[n]=0;
    //pd sufix
    for(i=n-1;i>0;i--)
       {maxim=1; pozurm=0;
        for(j=i+1;j<=n;j++)
           if(a[i]<=a[j] && maxim<1+lgmax[j])
             {maxim=1+lgmax[j]; pozurm=j;}
        lgmax[i]=maxim; urm[i]=pozurm;
       }
    //afisare
    maxim=lgmax[1]; pozmax=1;
    for(i=2;i<=n;i++)
        if(maxim<lgmax[i])
          {maxim=lgmax[i]; pozmax=i;}
    fout<<maxim<<'\n';
    while(pozmax)
         {fout<<pozmax<<' ';
          pozmax=urm[pozmax];
         }
    return 0;
}