Cod sursa(job #1704295)

Utilizator andreib888Balan Andrei andreib888 Data 18 mai 2016 16:08:18
Problema Subsir crescator maximal Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n;
vector<long long> v;
vector<int> lm, t;

void citire()
{
    long long a = 0;
    v.push_back(a); lm.push_back(a); t.push_back(a);
    f>>n;

    for(int i=1;i<=n;i++)
    {
        f>>a;
        v.push_back(a);
        lm.push_back(0);
        t.push_back(0);
    }
}

int lmax(int k)
{
    int lmx = 0, q;

    if(k == n)
        return 1;
    else
    {
        for(int i=k+1;i<=n;i++)
            if(v[i] > v[k] && lm[i] > lmx)
            {
                lmx = lm[i];
                q = i;
            }

        t[k] = q;
        return 1 + lmx;
    }
}

int main()
{
    int mx = 0, k;
    citire();

    for(int i=n;i>=1;i--)
    {
        lm[i] = lmax(i);
        if(lm[i] > mx)
        {
            mx = lm[i];
            k = i;
        }
    }

    g<<mx<<"\n";

    for(int i=k;i>0;i=t[i])
        g<<v[i]<<" ";
    return 0;
}