Cod sursa(job #1502393)

Utilizator DanutCNPR10Penciuc Danut DanutCNPR10 Data 14 octombrie 2015 16:56:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n , v[100000] , p , Max , poz[100000] , best[100000];
void citire()
{
    f>>n;
    for(int i=1 ; i<=n ; i++)
        f>>v[i];
}
void prelucrare()
{
    poz[n] = -1;
    best[n] = 1;
    Max = 1;
    p = n;
    for(int i = n - 1 ; i>=1 ;i--)
    {
        best[i] = 1;
        poz[i] = -1;
        for(int j = i + 1; j <= n ; j++)
        {
            if(v[i] < v[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                poz[i] = j;
                if(best[i] > Max)
                {
                    p=i;
                    Max = best[i];
                }
            }
        }
    }
}
void afisare()
{
    g<<Max<<'\n';
    while(p!=-1)
    {
        g << v[p] <<" ";
        p = poz[p] ;
    }

}
int main()
{
    citire();
    prelucrare();
    afisare();
    return 0;
}