Cod sursa(job #1322673)

Utilizator vlad_mose1928vlad mosessohn vlad_mose1928 Data 20 ianuarie 2015 11:42:44
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,v[100005],dp[100005],basescu[100005],vsol[100005];
int main()
{
    int i,dpmax,poz,j,maxim;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    dp[1]=1;
    basescu[1]=-1;
    for(i=2;i<=n;i++)
    {
        dpmax=0;
        poz=-1;
        for(j=i-1;j>=1;j--)
            if(v[j]<=v[i])
            {
                if(dp[j]>dpmax)
                {
                    dpmax=dp[j];
                    poz=j;
                }
            }
        dp[i]=1+dpmax;
        basescu[i]=poz;
    }
    maxim=0;
    for(i=1;i<=n;i++)
        if(dp[i]>maxim)
        {
            maxim=dp[i];
            poz=i;
        }
    g<<maxim<<endl;
    i=1;
    while(poz>=0)
    {
        vsol[i]=poz;
        poz=basescu[poz];
        i++;
    }
    for(j=i-1;j>=1;j--)
        g<<v[vsol[j]]<<" ";
    return 0;
}