Cod sursa(job #1098816)

Utilizator c0rn1Goran Cornel c0rn1 Data 5 februarie 2014 11:28:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f1=freopen("scmax.in", "r", stdin);
FILE *f2=freopen("scmax.out", "w", stdout);
int n, a[100001], l[100001];

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

void sol()
{
    for (int i=n-1; i>=0; i--)
    {
        l[i]=1;
        for (int j=i+1; j<n; j++)
            if (a[i]<a[j] && l[i]<l[j]+1)
                l[i]=l[j]+1;
    }
    int maxi=0, poz;
    for (int i=0; i<n; i++)
        if (l[i]>maxi)
        {
            maxi=l[i];
            poz=i;
        }
    printf("%d\n", maxi);
    for (int i=poz; i<n; i++)
    {
        printf("%d ", a[i]);
        int aux=l[i];
        while(aux!=l[i+1]+1)
            i++;
    }
}

int main()
{
    cit();
    sol();
    return 0;
}