De ce nu trece nimeni problema asta la categoria Prog dinamica > Knapsack ?

Bun, in O(n^2) iau 70 de puncte cu InOut fstream, cu extractor
Ideea e destul de simpla (pentru N^2)

Cod:

for (int i = N-1; i >= 0; i--)
    {
        d[i] = 1;
        for (int j = i+1; j < N; ++j)
            if (v[i].second == v[j].first && d[i] < d[j]+1) d[i] = d[j] + 1;
        if (Lmax < d[i]) Lmax = d[i], aux = v[i].first;
    }

Insa pentru liniara n-am nici cea mai vaga idee cum sa fac.
Imi dati niste sugestii, PLS?