Cod sursa(job #1787261)

Utilizator ion_1997Porcescu Ion ion_1997 Data 24 octombrie 2016 13:20:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int n , V[100001] , sol[100001] , ns , p;
int main()
{
    f >> n;
    for(int i = 1 ; i <= n ; ++i)
        f >> V[i];
        sol[n] = 1;
        ns = 1;
        p = n;
    for (int i = n - 1; i >= 1 ; --i )
    {
        int w = 0;
        for(int j = i + 1 ; j <= n ; ++j)
            if (sol[j] > w && V[j] > V[i])
            w = sol[j];
        sol[i] = w + 1;
        if ( ns < w + 1 )
            {ns = w + 1;
            p = i;}
    }
    g << ns << '\n' << V[p] << ' ';
    int k = p;
    p++; ns--;
    for (int i = p ; i <= n  ; ++i)
    {
        if ( sol[i] == ns && V[i] > V[k] )
        {
            g << V[i] << ' ';
            k = i;
            ns --;
        }
    }
    g.close();
    return 0;
}