Cod sursa(job #858675)

Utilizator cristitamasTamas Cristian cristitamas Data 19 ianuarie 2013 10:23:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
using namespace std;

int n,sir[100005],lg[100005];
int ind,max1;

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

void rezolvare(){
    int max,poz;
    for(int i=n-1;i>=0;--i){
        lg[i]=1;
        max=0;poz=-1;
        for(int j=i+1;j<n;++j)
            if(lg[j]>max && sir[j]>sir[i]){
                max=lg[j];
                poz=j;
            }
        lg[i]=1+max;
        if(lg[i]>max1){
           max1=lg[i];
           ind=i;
        }
    }
    printf("%d\n",max1);
}

void afisare(){
    printf("%d ",sir[ind]);
    for(int i=ind+1;i<n;++i)
        if(lg[i]==max1-1 && sir[i]>sir[ind]){
            max1=lg[i];
            ind=i;
            printf("%d ",sir[i]);
        }
}

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