Cod sursa(job #1391148)

Utilizator Daria09Florea Daria Daria09 Data 17 martie 2015 17:46:35
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int p[100001],a[100001],l[100001];
//Sa se determine un subsir al lui a
// care este ordonat strict crescator si care are lungimea maxima.
int main()
{
    int n,i,pmax;
    f>>n;
    for(i=1;i<=n;i++)f>>a[i];
    p[n]=-1;  l[n]=1;
    int j,max1=0;
    for(i=n-1;i>=1;i--)
    {
        p[i]=-1;
        l[i]=-1;
        for(j=i+1;j<=n;j++)
            if(l[i]<l[j+1]&&a[i]<a[j])
        {
            l[i]=l[j]+1;
            p[i]=j;
        }
        if(l[i]>max1)
        {
            max1=l[i];
            pmax=i;
        }
    }
    g<<l[pmax]<<'\n';
    j=pmax;
    while(j!=-1)
    {
        g<<a[j]<<" ";
        j=p[j];
    }
    return 0;
}