Cod sursa(job #1704300)

Utilizator andreib888Balan Andrei andreib888 Data 18 mai 2016 16:12:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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;

    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];
                t[k] = i;
            }
        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]<<" ";
/*
    for(int i=1;i<=n;i++)
        cout<<lm[i]<<" ";
    cout<<"\n";
    for(int i=1;i<=n;i++)
        cout<<t[i]<<" ";
    cout<<"\n"; */
    return 0;
}