Cod sursa(job #1335245)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 5 februarie 2015 11:51:19
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#define FIN "scmax.in"
#define FOUT "scmax.out"
#define maxsize 100002
using namespace std;

long long v[maxsize];
int l[maxsize];
int n;
int father[maxsize];

void read()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &n);

    for(int i=1;i<=n;i++)
        scanf("%lld ", &v[i]);

}

void solve()
{

    l[n] = 1;

    for(int i=n-1;i>0;i--)
    {
        int maxLen = l[i];
        int son = i;
        for(int j=i+1;j<=n;j++)
        {
            if(v[i] < v[j])
            {
                if(maxLen < l[j] )
                {
                    maxLen = l[j];
                    son = j;
                }
            }
        }

        l[i] = 1 + maxLen;
        father[i] = son;

    }


}

void write()
{
    int maxLen = l[1];
    int maxPos = 1;
    for(int i=2;i<=n;i++)
    {
        if(maxLen < l[i])
        {
            maxLen = l[i];
            maxPos = i;
        }

    }

    printf("%d \n", maxLen);

    do
    {
        printf("%d ", v[maxPos]);
        maxPos = father[maxPos];
    } while(v[maxPos]);


}

int main()
{
    read();
    solve();
    write();
    return 0;
}