Cod sursa(job #1860929)

Utilizator stefii_predaStefania Preda stefii_preda Data 28 ianuarie 2017 14:49:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

ifstream in ("scmax.in");
ofstream out ("scmax.out");
const int N = 100005;
int l[N], v[N], urm[N];//l[i]

int main()
{
    int n, i, j;
    in >> n;
    for(i = 1; i <= n; i++)
        in >> v[i];
    l[n] = 1;
    int maxi, k;
    urm[n] = n;
    for(i = n-1; i >= 1; i--)
    {
        maxi = 0; k = 0;
        for(j = i+1; j <= n; j++)
            if(v[i] < v[j] && l[j] > maxi)
                {
                    maxi = l[j];
                    k = j;
                }
        l[i] = maxi+ 1;
        if(k == 0)
            urm[i] = i;
        else urm[i] = k;
    }
    maxi = 0;
    for(i = 1; i <= n; i++)
        if(l[i] > maxi)
            {
                maxi = l[i];
                k = i;
            }
    out<<maxi<<"\n";
    out <<v[k]<<" ";
    while(k != urm[k])
    {
        k = urm[k];
        out <<v[k]<<" ";
    }



    return 0;
}