Cod sursa(job #1015945)

Utilizator tsubyRazvan Idomir tsuby Data 25 octombrie 2013 14:44:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#define N 100005
using namespace std;

int n, sir[N], L[N], urm[N], ind_max;

void citire(){
    scanf("%d\n",&n);
    for(int i = 0; i < n; i++)
        scanf("%d ",&sir[i]);
}

void rezolvare(){
    L[n-1] = 1;
    urm[n-1] = n-1;
    for(int i=n-2;i>=0;i--){
        urm[i] = i; //retine pozitia maximului din secventa (i+1,n)
        L[i] = 0;
        for(int j=i+1; j<n; j++)
            if(sir[i] < sir[j] && L[urm[i]] < L[j])
                urm[i] = j;
        L[i]= L[urm[i]]+1;
        if(L[i] > L[ind_max])
            ind_max=i;
    }
}

void afisare(){
    printf("%d\n", L[ind_max]);
    int i=ind_max;
    while(i != urm[i]){
        printf("%d ",sir[i]);
        i=urm[i];
    }
    printf("%d ",sir[i]);
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}