Cod sursa(job #1785926)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 22 octombrie 2016 09:49:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>

using namespace std;
int n, a[100000], l[100000];
struct Lm
{
    int indice, val;
}lmax;
int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
        l[n-1]=1;
    for(int i=n-2; i>=0; i--)
    {
        int maxi=0;
        for(int j=i+1; j<n; j++)
            if(a[j]>a[i])
                if(l[j]>maxi)
                maxi=l[j];
        l[i]=1+maxi;
        if(l[i]>lmax.val)
        {
            lmax.indice=i;
            lmax.val=l[i];
        }

    }

    printf("%d\n", lmax.val);
    printf("%d ", a[lmax.indice]);
    int x=lmax.val;
    int y=lmax.indice;
    for(int i=y+1; i<n; i++)
    {
        if(l[i]==x-1)
        {
            if(a[i]>a[y])
            {
                printf("%d ", a[i]);
                y=i;
                x--;
            }
        }
    }

    return 0;
}