Cod sursa(job #1487728)

Utilizator andreitulusAndrei andreitulus Data 17 septembrie 2015 13:09:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define Max 100005

int v[Max], n, ant[Max], dp[Max];


void read()
{
    int i;

    scanf("%d",&n);

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



void afis(int poz)
{

    if(poz == 0)
        return;

    afis(ant[poz]);

    printf("%d ", v[poz]);
}



void solve()
{
    int i, j, jmax, mmax, maxd = 0, imd;

    dp[1] = 1;

    for(i = 2; i <= n; i++)
    {
        mmax = 0;
        for(j = 1; j <= i-1; j++)
            if(dp[j] > mmax && v[j] < v[i])
            {
                mmax = dp[j]; jmax = j;
            }

        dp[i] = mmax + 1;

        if(mmax != 0) ant[i] = jmax;

        if(maxd < dp[i])
        {
            maxd = dp[i];
            imd = i;
        }
    }

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

    afis(imd);

}


int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    read();

    solve();

    return 0;
}