Cod sursa(job #2781338)

Utilizator borcanirobertBorcani Robert borcanirobert Data 9 octombrie 2021 10:25:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
using namespace std;

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

const int MAX = 100005;
int a[MAX];
int l[MAX];
int t[MAX];
int r[MAX];
int n;
int maxim, poz;

void Write( int i );

int main()
{
    int i, j;

    fin >> n;
    for ( i = 1; i <= n; i++ )
        fin >> a[i];

   /** for ( i = 1; i <= n; i++ )
    {
        l[i] = 1;
        for ( j = 1; j < i; j++ )
            if ( a[i] > a[j] && l[i] < l[j] + 1 )
            {
                l[i] = l[j] + 1;
                t[i] = j;
                if ( l[i] > maxim )
                    maxim = l[i], poz = i;
            }
    }  */

    for ( i = n; i >= 1; i-- )
    {
        r[i] = 1;
       /// for ( j = n; j > i; j-- )
        for ( j = i + 1; j <= n; j++ )
            if ( a[j] > a[i] && r[j] + 1 > r[i] )
            {
                r[i] = r[j] + 1;
                t[i] = j;
                if ( r[i] > maxim )
                    maxim = r[i], poz = i;
            }
    }

    fout << maxim << '\n';
    Write( poz );

    fin.close();
    fout.close();
    return 0;
}

void Write( int i )
{
    if ( i == 0 )
        return;
    fout << a[i] << ' ';
    Write( t[i] );
}