Cod sursa(job #1825570)

Utilizator MithrilBratu Andrei Mithril Data 9 decembrie 2016 13:51:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100001];
int parent[100001];
int best[100001];
int n;

void afisare(int pos)
{
    if(parent[pos]!=-1)
        afisare(parent[pos]);
    fout<<a[pos]<<' ';
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i+=1)
    {
        fin>>a[i];
        parent[i]=-1;
        best[i]=1;
    }
    for(int i=2;i<=n;i+=1)
    {
        for(int j=1;j<i;j+=1)
        {
            if(a[j]<a[i])
            {
                if(best[j]+1>best[i])
                {
                    best[i]=best[j]+1;
                    parent[i]=j;
                }
            }
        }
    }
    int max0=INT_MIN,pos;
    for(int i=1;i<=n;i+=1)
        if(best[i]>max0)
        {
            max0=best[i];
            pos=i;
        }
    fout<<max0<<'\n';
    afisare(pos);
    return 0;
}