c - 交替序列查找器

Question

我应该找到数组中最长的交替序列。

例如，-1 3 -4 5 -2 1 -7 5 5最长的序列是:-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);
}

这是我当前的代码，但在遇到零 (0) 时无法提供解决方案。有什么想法吗？

Answer 1

获取所有子序列的方法效率很低，因为序列中的切片数是O(N*N)。您可以在 O(N) 时间内实现这一点，只需遍历数组并保留迄今为止最长的交替切片。每当你发现交替切片结束时，你就重新开始计数，如果你超过了之前的分数，你就用新的分数代替它，依此类推。

假设 0 与其他所有符号具有相同的符号，以下代码包含给定示例 [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));
}

请记住，此代码还会打印序列开始的位置，仅用于调试目的。