Cod sursa(job #1358847)

Utilizator mist.moonDenisa Gherghel mist.moon Data 24 februarie 2015 20:13:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include<stdio.h>
using namespace std;
int a[100002],l[100002],ant[100002],n,i,j,lmaxi,pmaxi,maxi=1,maxp;
void afisare(int i)
{
    if(ant[i]==0) cout<<a[i]<<" ";
    else {
        afisare(ant[i]);
        cout<<a[i]<<" ";
    }
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    l[1]=1; ant[1]=0;
    for(i=2;i<=n;i++)
    {
        lmaxi=0; pmaxi=0;
        for(j=i-1;j>=1;j--)
            if(a[j]<a[i])
            {
                 if(l[j]>=lmaxi) { lmaxi=l[j]; pmaxi=j; if(lmaxi>maxi) j=0; }
            }
        l[i]=lmaxi+1; ant[i]=pmaxi;
        if(l[i]>maxi){ maxi=l[i]; maxp=i;}
    }
    cout<<maxi<<endl;
    afisare(maxp);
    return 0;
}