Cod sursa(job #2133583)

Utilizator ApetriiRaduApetrii Radu ApetriiRadu Data 17 februarie 2018 10:19:32
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define NMAX 1000

using namespace std;
ifstream fin("sir.in");
ofstream fout("sir.out");

int a[NMAX];
int lgmax[NMAX];
int urm[NMAX];
int n,i,maxim,urmator,j,pozmax;
int main()
{fin>>n;
 for(i=0;i<n;i++)
    fin>>a[i];
 lgmax[n-1]=1;
 urm[n-1]=-1;
 // cel mai cel mic sufix are un element
 for(i=n-2;i>=0;i--)
    {maxim=1;
     urmator=-1;
     for(j=i+1;j<n;j++)
        if(a[i]<=a[j] && 1+lgmax[j]>maxim)
          {maxim=1+lgmax[j];
           urmator=j;
          }
     lgmax[i]=maxim;
     urm[i]=urmator;
    }
 //afisare
 maxim=lgmax[0];
 pozmax=0;
 for(i=1;i<n;i++)
     if(maxim<lgmax[i])
       {maxim=lgmax[i];
        pozmax=i;
       }
 fout<<maxim<<'\n';
 fout<<a[pozmax]<<' ';
 while(urm[pozmax]!=-1)
      {pozmax=urm[pozmax];
       fout<<a[pozmax]<<' ';
      }
 fout<<'\n';
 fout.close();
 return 0;
}