Cod sursa(job #1523540)

Utilizator RomitanRomitan Raul Romitan Data 12 noiembrie 2015 20:29:04
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
/*Se da un sir cu n elemente numere naturale.
Sa se determine lungimea celui mai lung subsir crescator din sir, apoi elementele subsirului respectiv*/
///PROGRAMARE DINAMICA
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
int n, i, j, x[1000], l[1000], ant[1000], maxx, lmax, pmax;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
        f>>x[i];

    for(i=1;i<=n;i++)
    {   lmax=0;
        ant[i]=0;
        for(j=1;j<=i-1;j++)
            if(x[i]>x[j] && l[j]>lmax)
            {   lmax=l[j];
                ant[i]=j;
            }
        l[i]=1+lmax;
        if(maxx<l[i])
        {   maxx=l[i];
            pmax=i;
        }
    }
    /*for(i=1;i<=n;i++)
        cout<<ant[i]<<' ';*/
    g<<maxx<<endl; //lungimea celui mai lung subsir crescator din sir

    for(i=pmax;i>=1;i=ant[i])
        g<<x[i]<<' ';
    return 0;
}