Cod sursa(job #2314550)

Utilizator petru123456789Petru B petru123456789 Data 8 ianuarie 2019 18:39:31
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include<fstream>

using namespace std;
int n,i,j,a[100005],s[100005],u,poz[100005],w[100005],q,maxim,imax,p;
int main()
{
    ifstream in("scmax.in");
    ofstream out("scmax.out");
    in>>n;
    s[n]=1;
    poz[n]=-1;
    maxim=1;
    p=n;
    for(i=1;i<=n;i++)
    {
        in>>a[i];
    }
    for(i=n-1;i>=1;i--)
    {
        s[i]=1;
        poz[i]=-1;
        for(j=i+1;j<=n;j++)
        {
            if(a[i]<a[j] && s[i]<s[j]+1)
            {
                s[i]=s[j]+1;
                poz[i]=j;
                if(s[i]>maxim)
                {
                    maxim=s[i];
                    p=i;
                }
            }

        }
    }
    out<<maxim<<'\n';

    while(p!=-1)
    {
        u++;
        w[u]=a[p];
        p=poz[p];

    }
    for(i=1;i<=u;i++)
    {
        out<<w[i]<<' ';
    }
}