Cod sursa(job #1325719)

Utilizator tudor00Stoiean Tudor tudor00 Data 24 ianuarie 2015 11:58:18
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,v[100005],dp[100005],pred[100005],vsol[100005];
int main()
{
    int i,dpmax,poz,j,maxi;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    dp[1]=1;
    pred[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;
        pred[i]=poz;
    }
    maxi=0;
    for(i=1;i<=n;i++)
        if(dp[i]>maxi)
        {
            maxi=dp[i];
            poz=i;
        }
    out<<maxi<<'\n';
    i=1;
    out<<poz;
    while(poz!=-1)
    {
        vsol[i]=poz;
        poz=pred[poz];
        i++;
    }
    for(j=i-1;j>=1;j--)
    out<<v[vsol[j]]<<" ";
    in.close();
    out.close();
    return 0;
}