Cod sursa(job #1600553)

Utilizator andrei_bB. Andrei andrei_b Data 15 februarie 2016 09:53:49
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;

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

int n,v[100005],s[100005],p[100005];

void afisare( int maxim , int poz ){

    if ( maxim==0 )
        return;
    afisare(maxim-1,p[poz]);
    fout<<poz<<' ';

    return;
}

void subsir( int &maxim , int &poz ){

    s[1]=1;
    for ( int i=2 ; i<=n ; i++ ){
        maxim=0;
        for ( int j=1 ; j<=i ; j++ ){
            if ( v[i]>v[j] && s[j]>=maxim ){
                maxim=s[j];
                p[i]=j;
            }
        }
        s[i]=1+maxim;
    }
    maxim=0;
    for ( int i=1 ; i<=n ; i++ )
        if ( s[i] >= maxim ){
            maxim=s[i];
            poz=i;
        }
}

int main()
{
    int maxim,poz;
    fin>>n;
    for ( int i=1 ; i<=n ; i++ )
        fin>>v[i];
    subsir(maxim,poz);
    fout<<maxim<<'\n';
    afisare(maxim,poz);
}