ZigZag - Problema de dinamica

[•alexandru92]

Am urmatoarea problema:
Se numeste o secventa in ZigZag daca alterneaza diferentele dintre elmentele consecutive. De exemplu sirul 1,7,4,9,2,5  este in ZigZag ( diferentele 6,-3,5,-7,3  ). Dat un sir de numere sa se determine cel mai lung subsir de elemente in ZigZag.
Am aplicat aceeasi dinamica ca si la subsirul crescator maximal numai ca mai retin intr-un vector alternate  ( 0 - diferenta dintre ultimul si antepenultimul element din sir este negativa, 1 daca este pozitiva si 2 daca sirul e format dintr-un singur element ) si un vector topelement unde retin ultimul numar introdus in sir.
Am scris urmatorul cod, dar nu imi dau seama unde gresesc ( pentru sirul din exemplu da 3 in loc de 6 ).

Cod:

#define pb push_back
int longestZigZag( vector<int> sequence )
{
    if( sequence.size() <= 2 )
        return sequence.size();
    int n=sequence.size(), i, j, maxim, maxim2=1, poz, sg, sign;
    vector<int> L, topelement=sequence, alternate;
    L.pb(1); alternate.pb(2);
    for( i=0; i < n; ++i )
    {maxim=0; poz=-1;
        for( j=0; j < i; ++j )
        {
            if( alternate[j] < 2 )
            {
                sign=(sequence[i]-topelement[j]) >= 0;
                if( sign != alternate[j] && L[j] > maxim )
                    maxim=L[j], poz=j, sg=sign;
            }
            else if( L[j] > maxim )
                    maxim=L[j], poz=j, sg=(sequence[i]-sequence[j]) >= 0;
        }
        L.pb(maxim+1);
        if( -1 != poz )
        {
            alternate.pb( sg );
            alternate[poz]=sg;
            topelement[poz]=sequence[i];
        }
        else alternate.pb(2);
        maxim2=max( L.back(), maxim2 );
    }
    return maxim2;
}

[•toni2007]

Eu ma gandeam asa: ti un C[ i ] lungimea maxima sa ai ultimul element din subsir pe i si penultimul mai mare ca v[ i ]. D[ i ]lungimea maxima sa ai ultimul element din subsir pe i si penultimul mai mic ca v[ i ], si E[ i ] = 1.

Cod:

C[i] = suma(D[j]) (pt j < i, v[j] > v[i]) + suma(E[j]) (pt j < i, v[j] > v[i])
D[i] = suma(C[j]) (pt j < i, v[j] < v[i]) + suma(E[j]) (pt j < i, v[j] < v[i])
E[i] = 1

[•wefgef]

Problema merge rezolvata in O(N log N) intr-un mod asemanator cu algoritmul de gasire a celui mai lung subsir crescator.