Cod sursa(job #2114595)

Utilizator vladboss2323Ciorica Vlad vladboss2323 Data 25 ianuarie 2018 17:44:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

const int N=100005;

int a[N],d[N],n,inceput[N];
int maxim;

void sol(int x)
{
    if(x!=0)
        sol(inceput[x]);
    if(x>0)
    out<<a[x]<<" ";
}
int main()
{
    int poz,i,j,x,y;
    /*
    dp[i] = lungimea celui mai lung subsir crescator care se termina pe pozitia i
    dp[i] = 1 + max {dp[j] | j < i si v[j] < v[i]}
    */
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>a[i];
        d[i]=1;
    }
    for(i=2; i<=n; i++)
    {
        for(j=1; j<i; j++)
        {
            if(a[i]>a[j] && d[i]<d[j]+1)
            {
                d[i]=1+d[j];
                inceput[i]=j;
            }
        }
    }
    for(i=1; i<=n; i++)
        if(d[i]>maxim)
        {
            maxim=d[i];
            poz=i;
        }
    out<<maxim<<'\n';
    sol(poz);
    return 0;
}