Cod sursa(job #1854757)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 23 ianuarie 2017 11:02:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#define nmax 100001

using namespace std;

ifstream fin ( "scmax.in" );
ofstream fout ( "scmax.out" );

int a[nmax], lg[nmax], t[nmax], sol[nmax];

int main()
{   int n, i, m, j;
    int lgmax, imax;
    fin >> n;
    for ( i = 1; i <= n; i++ )
         fin >> a[i];
    fin.close();
    lg[1] = 1;
    t[1] = 0;
    for ( i = 2; i <= n; i++ )
         { lg[i] = 1;
           t[i] = 0;
           for ( j = 1; j <= i - 1; j++ )
                if ( a[j] < a[i] && lg[j] + 1 > lg[i] )
                    { lg[i] = lg[j] + 1;
                      t[i] = j;
                    }
         }
    lgmax = 0;
    for ( i = 1; i <= n; i++ )
         if ( lg[i] > lgmax )
             { lgmax = lg[i];
               imax = i;
             }
    m = 1;
    sol[1] = a[imax];
    while ( t[imax] )
           { imax = t[imax];
             m++;
             sol[m] = a[imax];
           }
    fout << lgmax << "\n";
    for ( i = m; i >= 1; i-- )
         fout << sol[i] << " ";
    fout << "\n";
    fout.close();
    return 0;
}