Cod sursa(job #2297224)

Utilizator DragescuLeonardDragescuLeonard DragescuLeonard Data 5 decembrie 2018 16:29:07
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

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

int n,a[100010],m[10010][10010],i,j,nr,s,sol[100010],maxim,imax,ma;

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    for(i=1;i<=n;i++)
    {
        nr=a[i];
        s=1;
        for(j=i;j<=n;j++)
    {
        if(nr<a[j])
        {
            nr=a[j];
            s++;
        }
        m[i][j]=s;

    }
        s=0;
    }
    maxim=m[1][n];
    imax=1;
    for(i=2;i<=n;i++)
        {
            if(m[i][n]>maxim)
            {
                maxim=m[i][n];
                imax=i;
            }
        }
    ma=maxim;
    i=n;
    while(m[imax][i])
    {
        if(m[imax][i]==maxim && m[imax][i-1]==maxim-1)
        {
            sol[maxim]=a[i];
            maxim--;
        }
        i--;
    }
    fout<<ma<<endl;
    for(i=1;i<=ma;i++)
        fout<<sol[i]<<" ";
}