Cod sursa(job #2040663)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 16 octombrie 2017 10:17:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100001],v[100001],n,maxi,rez,st[100001],poz,x;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        maxi=0;
        for(int j=i;j>0;j--)
        {if(maxi<v[j]&&a[j]<a[i])
            maxi=v[j];

        }
        v[i]=maxi+1;
        if(v[i]>rez)
        {
            rez=v[i];
            poz=i;
        }
    }
    x=rez;
    int k=1;
    for(int i=poz;i>0;i--)
    {
        if(v[i]==x)
        {
            st[k]=a[i];
            k++;
            x--;
        }
    }
    cout<<rez<<"\n";
    for(int i=rez;i>0;i--)
    {
        cout<<st[i]<<" ";
    }

    return 0;
}