Cod sursa(job #678563)

Utilizator ghegoiu1Ghegoiu Stefan ghegoiu1 Data 11 februarie 2012 22:20:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#define MAX 100000
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[MAX],b[MAX],p[MAX];
int M,m,i,n,j,fin;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
        f>>a[i];
    M=1;
    m=0;
    b[n]=1;
    for (i=n-1;i>=1;i--)
        {
            M=0;
            for (j=i+1;j<=n;j++)
                if (a[i]<a[j] && M<b[j])
                     {
                        M=b[j];
                        p[i]=j;
                     }
            b[i]=M+1;
            if (b[i]>m) {
                m=b[i];
                fin=i;
            }
        }
    g<<m<<'\n';
    i=fin;
    while (i!=0)
    {
        g<<a[i]<<' ';
        i=p[i];
    }
    return 0;
}