c - 找到最长的子序列的长度，其中包含多个连续的 k 个 0，然后是多个连续的 k 个 1

Question

给定一个由 0 和 1 组成的数组，找出包含连续 k 个 0 后跟连续 k 个 1 的最长子序列的长度。

注意:有可能你的子序列前有0，后有1，但不能同时发生，否则你的子序列不是最长的。

找到一个非常复杂的算法。

这就是我目前的状态。

int subsequence(int v[], int dim){
int i, k_0=0, k_1=0, count_0=0, count_1=0, prev=-1;
for (i = 0; i < dim; i++) {

    if (v[i] == 0 && prev == 1) {
        count_0 = 0;
        count_1 = 0;
        k_0 = k_1 = (k_0 < k_1) ? k_0 : k_1;
    }

    if (v[i] == 0) {
        count_0 += 1;
    }

    if (v[i] == 1) {
        count_1 += 1;
    }

    k_0 = (count_0 > k_0) ? count_0: k_0;
    k_1 = (count_1 > k_1) ? count_1: k_1;
    prev = v[i];
}
return (k_0 < k_1) ? k_0 : k_1;

Complexity O(n)

有没有更好的方法来解决这个问题？

Answer 1

更好的方法是使用更清晰的算法实现正确声明和定义函数。

第一个参数应具有限定符const，第二个参数应具有类型size_t。并且函数返回类型也应该是size_t。

在该函数中，您应该首先找到等于 0 的第一个元素，然后才处理数组的其余部分。

我会这样写函数

#include <stdio.h>

size_t longest_subsequence( const int a[], size_t n )
{
    const int value1 = 0;
    const int value2 = 1;

    size_t longest = 0;

    size_t i = 0;
    while ( i < n && a[i] != value1 ) i++;

    while ( i < n )
    {

        size_t n1 = i;

        while ( i < n && a[i] == value1 ) i++;

        size_t n2 = i;

        while ( i < n && a[i] == value2 ) i++;

        n1 = n2 - n1;
        n2 = i - n2;

        n1 = n2 < n1 ? n2 : n1;

        if ( longest < 2 * n1 ) longest = 2 * n1;
    }

    return longest;
}

int main(void) 
{
    int a[] = { 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1 };
    const size_t N = sizeof( a ) / sizeof( *a );

    printf( "%zu\n", longest_subsequence( a, N ) );

    return 0;
}

程序输出为

6

确实数组最长的子序列是

{ 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1 };
                                ^^^^^^^^^^^^^^^^

或者计算出的值可以是这样的

if ( longest < n1 ) longest = n1;

原则上，如何计算它并不重要。