Cod sursa(job #1319695)

Utilizator chiturobertChitu Robert Alexandru chiturobert Data 17 ianuarie 2015 12:43:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,pred[100005],v[100005],dp[100005],d[100005];
int main()
{
    int i,dpmax,j,poz,maxim=0;
    f>>n;
    dp[1]=1;
    pred[1]=-1;
    for(i=1;i<=n;i++)
        f>>v[i];

        for(i=1;i<=n;i++)
        {
        poz=-1;
            dpmax=0;
            for(j=i;j>=1;j--)
            {
                if(v[j]<v[i])
                {
                    if(dp[j]>dpmax)
                    {
                        dpmax=dp[j];
                        poz=j;
                    }
                }
            }
            dp[i]=1+dpmax;
            pred[i]=poz;
        }


        for(i=1;i<=n;i++)
        if(dp[i]>maxim)
        {
            maxim=dp[i];
            poz=i;
        }
        g<<maxim<<'\n';
i=1;
        while(poz!=-1)
        {
            d[i]=poz;
            poz=pred[poz];
            i++;
        }
        for(j=i-1;j>=1;j--)
        {
            g<<v[d[j]]<<" ";
        }
        g<<'\n';
        f.close();
        g.close();

    return 0;
}