Cod sursa(job #3211569)

Utilizator miruna.abAbaianiti Miruna miruna.ab Data 9 martie 2024 15:22:54
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long long int n, i, v[100001], e[100001], k, j, m, maxx1, maxx, c, a[100001];
long long int inf=INT_MIN;
int main()
{
    fin>>n;
    for(i=0; i<n; i++){fin>>v[i]; e[i]=1;}
    for(k=0; k<n; k++){
        for(i=0; i<k; i++)if(v[k]>v[i]){
            e[k]=max(e[k], e[i]+1);
        }
    }
    m=n-1;
    fout<<e[n-1]<<endl;
    k=e[n-1];
    maxx=inf;
    a[k]=INT_MAX;
    for(i=k; i>=1; i--){
       for(j=m; j>=0; j--){if(e[j]==i&&v[j]<a[i]){maxx1=maxx; maxx=max(v[j],maxx); if(maxx1!=maxx)c=j;}}
       a[i-1]=maxx;
       maxx=inf;
       m=c;
   }
   for(i=0; i<k; i++)fout<<a[i]<<' ';
}