Cod sursa(job #3259998)

Utilizator chiarimitrebuiecontquestionmarkmiruna mihailescu chiarimitrebuiecontquestionmark Data 28 noiembrie 2024 19:51:51
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
using namespace std;
int v[100001], d[100001], last[100001], solutie[100001];
int main(){
  ifstream fin("scmax.in");
  ofstream fout("scmax.out");
  int n, x, dmax=1, lasti;
  fin>>n>>v[1];
  d[1]=1;
  for(int i=2;i<=n;i++){
    fin>>v[i];
    d[i]=1;
    for(int k=i-1; k>1; k--){
      if(v[k]<v[i]){
        if(d[i]<d[k]+1){
          d[i]=d[k]+1;
          last[i]=k;
        }
      }
    }
    if(dmax<d[i])
      dmax=d[i], lasti=i;;
  }
fout<<dmax<<endl;
int j=0;
while(j<=dmax){
  solutie[++j]=v[lasti];
  lasti=last[lasti];
}
for(int i=dmax; i>=1; i--){
  fout<<solutie[i]<<" ";

}


}