Cod sursa(job #1045625)

Utilizator aidutzaAida Denisa aidutza Data 1 decembrie 2013 20:15:44
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#define N 100010
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[N],p[N],l[N],k;
long n;
void citeste()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f.close();
}
void init()
{
    l[n]=1;
    p[n]=n;
}
void pd_sc()
{
    int i,j;
    for(i=n-1;i>=1;i--)
    {
        l[i]=1;
        p[i]=i;
        for(j=i+1;j<=n;j++)
        if(a[i]<=a[j]&&l[i]<=l[j])
        {
            l[i]=l[j]+1;
            p[i]=j;
        }
    }
}
void cauta()
{
    int maxim=-1;
    int i;
    for(i=1;i<=n;i++)
        if(l[i]>maxim)
        {
            maxim=l[i];
            k=i;
        }
}
int main()
{
    int i,j;
    citeste();
    pd_sc();
    cauta();
    g<<l[k];
    g<<'\n';
    for(i=1,j=k;i<=l[k];i++,j=p[j])
        g<<a[j]<<" ";
    g.close();
    return 0;
}