Cod sursa(job #2153524)

Utilizator elenaisaiaElena Isaia elenaisaia Data 6 martie 2018 11:53:03
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;

long long a[100010],b[100010],t[100010];
int n;
ofstream fout("scmax.out");

void afisare(int i)
{
    if(t[i]==-1)
    {
        fout<<a[i]<<" ";
        return;
    }
    afisare(t[i]);
    fout<<a[i]<<" ";
}

int main()
{
    ifstream fin("scmax.in");
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>a[i];
    b[0]=1;
    t[0]=-1;
    int maxim=0,poz=0;
    for(int i=0;i<n;i++)
    {
        int pozmax=-1,nrmax=0;
        for(int j=i-1;j>=0;j--)
            if(b[j]>nrmax&&a[i]>a[j])
            {
                nrmax=b[j];
                pozmax=j;
            }
        b[i]=nrmax+1;
        t[i]=pozmax;
        if(maxim<b[i])
        {
            maxim=b[i];
            poz=i;
        }
    }
    fout<<b[n-1]<<"\n";
    for(int i=0;i<n;i++)
        cout<<t[i]<<" ";
    afisare(poz);
    return 0;
}