Cod sursa(job #1984188)

Utilizator Constantin.Dragancea Constantin Constantin. Data 23 mai 2017 22:38:10
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
using namespace std;
ifstream cin ("scmax.in");
ofstream cout ("scmax.out");

int n, A[100010],D[100010],poz[100010],m;

void afisare(int q){
    if (poz[q]!=0) afisare(poz[q]),cout<<A[q]<<" ";
    else cout<<A[q]<<" ";
}

int main(){
    cin>>n;
    for (int i=1; i<=n; i++) cin>>A[i],D[i]=1;
    D[1]=1;
    for (int i=2; i<=n; i++){
        D[i]=D[i-1]; poz[i]=poz[i-1];
        for (int j=i-1; j; j--){
            if (A[i]>A[j] && D[j]+1>D[i]) D[i]=D[j]+1,m=A[i],poz[i]=j;
        }
    }
    cout<<D[n]<<"\n";
    afisare(poz[n]);
    cout<<m<<" ";
    return 0;
}