Cod sursa(job #2000999)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 15 iulie 2017 14:01:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
using namespace std;
int N,v[100001],scm[100001],poz[100001],idx,Max;
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
        scanf("%d",&v[i]),scm[i]=1;
    Max=1,idx=N,poz[N]=-1;
    for(int i=N-1;i>=1;--i){
        poz[i]=-1;
        for(int j=i+1;j<=N;++j)
            if(v[i]<v[j] && scm[i]<scm[j]+1){
                    scm[i]=scm[j]+1,poz[i]=j;
                    if(scm[i]>Max)Max=scm[i],idx=i;
            }
    }
    printf("%d\n",Max);
    int k=idx;
    while(k!=-1){
        printf("%d ",v[k]);
        k=poz[k];
    }
    return 0;
}