Cod sursa(job #2107485)

Utilizator busonica12Sofrone Mihnea Andrei busonica12 Data 17 ianuarie 2018 12:00:20
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>

using namespace std;

int g[100001];
int main()
{
    int n,k,i,v[100001],max=1,f=1,j;
    ifstream q("scmax.in");
    ofstream w("scmax.out");
    q>>n;
    g[n]=1;
    for(i=1;i<=n;i++) q>>v[i];
    for(i=n-1;i>=1;i--)
    {
        g[i]=0;
        for(j=i+1;j<=n;j++)
        {
            if(v[i]<v[j]&&g[j]>=max) {g[i]=g[j]+1;}
            if(g[i]>max) {max=g[i];f=i;}
        }
    }
    w<<max<<endl;
    k=max;
    for(i=1;i<=n;i++)
    {
        if(i==f) {w<<v[i]<<" ";k--;}
        if(g[i]==k) {w<<v[i]<<" ";k--;}
    }

    return 0;
}