Cod sursa(job #1010669)

Utilizator jul123Iulia Duta jul123 Data 15 octombrie 2013 13:30:58
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<iostream>
#include<fstream>
#include<cmath>

using namespace std;

int st[9], n;     
int main()
{
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    int n, i, a, lgmax, j, prec[100000], v[100000],imax, max, lg[100000];
    f>>n;
    for(i=0; i<n; i++)
         f>>v[i];
    lg[0]=1;
    for(i=1;i<n;i++)
    lg[i]=0;
    for(i=1; i<n; i++)
    {
                    for(j=0; j<=i-1; j++)
                    {
                                       max=0;
                                       if( (v[i]>v[j]) && (lg[j]>max) ) 
                                                   {
                                                        max=lg[j];
                                                        prec[i]=j;
                                                   }
                    }
                    lg[i]=max+1;
                    if(max==0)
                              prec[i]=0;
    }
    max=0;
    for(i=0; i<n; i++)
             if(lg[i]>max)
             {
             imax=i;
            max=lg[i];
             }    
    a=imax;
    lgmax=lg[a];
    g<<lg[a]+1<<"\n";
    for(i=1; i<=lgmax+1; i++)
             {
                       g<<v[a]<<" ";
                       a=prec[a];
             }
                
            
    f.close();
    g.close();
    return 0;
}