CODEWITHSUNDEEP
calgorithmdata-structures
Hydroxis
Hydroxis

Reputation: 95

Alternating sequence finder

I'm supposed to find the longest alternating sequence in an array.

For example, -1 3 -4 5 -2 1 -7 5 5 The longest sequence is: -1 3 -4 5 -2 1 -7 5

int ZigZag(int a[], int N) 
{
int i;
int j;

int z = 0;

int dolzina = 0;

node *result = NULL;

int prethodenZnak = getSign(a[0]);

for(i = 0; i < N; i++)
{
    for(j = i; j < N; j++)
    {
        if(a[j] == 0)
            a[j] = prethodenZnak;

        if(getSign(a[j]) != prethodenZnak)
        {
            dolzina++;
            prethodenZnak = getSign(a[j]);
        }
        else
            break;
    }
    append(&result, dolzina+1);

    dolzina = 0;
}

return max(result);
}

This is the current code that I have, but It's failing to provide a solution when a zero(0) is encountered. Any ideas?

Upvotes: 0

Views: 486

Answers (1)

pevasquez
pevasquez

Reputation: 862

The approach of getting all subsequences is very inefficient, as the number of slices in a sequence is O(N*N). You can achieve this in O(N) time by just iterating over the array and keeping the longest alternating slice so far. Whenever you find an alternating slice ends, you just start counting again, and if you beat the previous score, you replace it with the new one, and so on.

Assuming that 0 has the same sign as everything else, the following code includes the given example [8 -1 0 2 -1 3 -8 2 -3]:

int alternates(int current, int previous){
    return (current > 0 && previous < 0) || (current < 0 && previous > 0);
}

int zigzag(int a[], int N){
    int currentLength = 1, longest = 1, longestStart = 0, currentStart = 0;

    for(int i = 1; i<N; ++i){
        currentLength = alternates(a[i], a[i-1])? currentLength+1 : 1;

        if(currentLength == 1)
            currentStart = i;

        if(currentLength > longest){
            longest = currentLength;
            longestStart = currentStart;
        }
    }

    printf("position = %d\n", longestStart);

    return longest;
}

int main(int argc, char **argv){
    int example[] = {8, -1, 0, 2, -1, 3, -8, 2, -3};
    printf("RESULT: %d\n", zigzag(example, 9));
}

Keep in mind that this code also prints where the sequence starts, just for debugging purposes.

Upvotes: 1

Related Questions