Cod sursa(job #3337440)

Utilizator Andrei_PanaAndrei Pana Andrei_Pana Data 27 ianuarie 2026 18:47:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;

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

#define MAXN 100000

int v[MAXN+1],maxl[MAXN+1],nextpos[MAXN+1];

int main(){
  int n,i;

  cin>>n;
  for(i=1;i<=n;i++){
    cin>>v[i];
  }

  maxl[n]=1;
  nextpos[n]=0;
  for(i=n-1;i>=1;i--){
    maxl[i]=1;
    for(int j=i+1;j<=n;j++){
      if(v[j]>v[i]&&maxl[j]+1>maxl[i]){
        maxl[i]=maxl[j]+1;
        nextpos[i]=j;
      }
    }
  }

  int pos=1;
  for(i=2;i<=n;i++){
    if(maxl[i]>maxl[pos]){
      pos=i;
    }
  }

  cout<<maxl[pos]<<"\n";
  do{
    cout<<v[pos]<<" ";
    pos=nextpos[pos];
  }while(pos);

  return 0;
}