Cod sursa(job #1848282)

Utilizator lauratalaatlaura talaat lauratalaat Data 15 ianuarie 2017 18:45:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
int v[100001],v2[100001];
struct bine { int nr ; int pozitie ;};
bine lung[100001];
int main(){
    int n,pozi,i,j,maxim,poz,max,cp;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    lung[1].nr=1;
    maxim=1;
    for(i=2;i<=n;i++){
        max=0;poz=0;
        for(j=i-1;j>=1;j--)
            if(v[i]>v[j]&&lung[j].nr>max){
                max=lung[j].nr;
                poz=j;
            }
        lung[i].nr=max+1;
        lung[i].pozitie=poz;
        if(lung[i].nr>maxim){
            maxim=lung[i].nr;
            pozi=i;
        }
    }
    cp=maxim;
    printf("%d\n",maxim);
    v2[maxim]=v[pozi];
    maxim--;
    while(maxim!=0){
        v2[maxim]=v[lung[pozi].pozitie];
        pozi=lung[pozi].pozitie;
        maxim--;
    }
    for(i=1;i<=cp;i++)
        printf("%d ",v2[i]);
    return 0;
}