Cod sursa(job #950093)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 15 mai 2013 20:41:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstdio>
using namespace std;
int i, n, a[100001], v[100001], vc[100001], maxf, poz, mx, j, mff;
int main(){
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d", &n);
    for (i=1;i<=n;i++) scanf("%d", &a[i]);
    maxf=-1; poz=-1; v[1]=1;
    for (i=2;i<=n;i++) {
        mx=0;
        for (j=i-1;j>=1;j--)
            if ((v[j]>mx)&&(a[j]<a[i]))
                mx=v[j];
        v[i]=mx+1; if (v[i]>maxf) {maxf=v[i]; poz=i;}
    }
    printf("%d\n", maxf);
    mff=maxf;
    vc[maxf]=a[poz];
    maxf--;
    for (i=poz-1;i>=1;i--)
        if (v[i]==maxf) {vc[maxf]=a[i]; maxf--;}
    printf("%d", vc[1]); for (i=2;i<=mff;i++) printf(" %d", vc[i]);
    printf("\n"); return 0;
}