0

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?

Hydroxis
  • 95
  • 1
  • 12
  • 2
    I assume you mean the longest alternating of signs sequence? There is no 'right' or 'wrong' answer for that concerning 0 - you must specify what behavior you want. – orlp Oct 25 '15 at 00:44
  • A 0 counts as the same sign as previous. – Hydroxis Oct 25 '15 at 00:48
  • You should provide a compiling example at least. Is the linked list actually needed for anything or just something you are using? What is the `node` type's definition? Do you have the original statement of the problem? Do you just need the length or also the position in the input array? – pevasquez Oct 25 '15 at 02:02
  • The way I'm doing it is I use bruteforce to find the lenght of all sequences and store the results in a list and then find the maximum element of the list which represents the longest lenght. – Hydroxis Oct 25 '15 at 02:06
  • Something must be wrong with the way I'm handling it, because It's failing for the following sequence: 8 -1 0 2 -1 3 -8 2 -3 – Hydroxis Oct 25 '15 at 02:08
  • So, you want a fix for your way of solving it or can I propose another solution? – pevasquez Oct 25 '15 at 02:12
  • I know there's a dynamic solution for the problem and if you can propose one that'd be nice (I haven't started to practise yet). – Hydroxis Oct 25 '15 at 02:14

1 Answers1

1

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.

pevasquez
  • 862
  • 8
  • 14