Cod sursa(job #2123302)

Utilizator georgianamaximMaxim Georgiana georgianamaxim Data 6 februarie 2018 02:13:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#define DN 100001

using namespace std;

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

int n, d[DN], ind, poz[DN], m;
long long a[DN];

int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>a[i];
    d[1]=1;
    for(int i=n; i>=1; i--)
    {
        d[i]=1;
        poz[i]=0;
        for(int j=i+1; j<=n; j++)
            if(a[i]<a[j] && d[i]<1+d[j])
            {
                d[i]=1+d[j];
                poz[i]=j;
            }
        if(m<d[i])
        {
            ind=i;
            m=d[i];
        }
    }
    g<<m<<'\n';
    for(int i=ind; i>0; i=poz[i])
        g<<a[i]<<" ";
    return 0;
}