Cod sursa(job #2129828)

Utilizator agatha_m_sMihalcea Agatha agatha_m_s Data 13 februarie 2018 10:00:32
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int N,i,a[100005],lmax,L[100005],Max,poz,ult,nr,b[100005],j;
int main()
{
    f>>N;
    for(i=1; i<=N; i++)  f>>a[i];
    L[i]=1;
    lmax=1;
    for(i=2; i<=N; i++)
    {
        Max=0;
        for(j=i-1; j>=1; j--)
        {
            if(Max<L[j]&&a[i]>a[j])  Max=L[j];
            L[i]=1+Max;
            if(L[i]>lmax)
            {
                lmax=L[i];
                poz=i;
            }
        }
    }
    nr=1;
    b[nr]=a[poz];
    ult=a[poz];
    lmax--;
    for(i=poz-1; i>=1; i--)
    {
        if(a[i]<ult&&L[i]==lmax)
        {
            nr++;
            b[nr]=a[i];
            lmax--;
            ult=a[i];
        }
    }
    g << nr << '\n';
    for(i=nr; i>=1; i--)  g<<b[i]<<" ";
    return 0;
}