c - 求出包含多个连续k 0s以及随后多个连续k 1s的最长子序列的长度

给定一个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)

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

最佳答案

更好的方法是通过更清晰的算法实现正确地声明和定义函数。
第一个参数应具有限定符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;

主要的是，如何计算并不重要。

关于c - 求出包含多个连续k 0s以及随后多个连续k 1s的最长子序列的长度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57994039/