给定一个0和1的数组，请找出最长子序列的长度，该子序列包含多个连续的k 0s，然后是多个连续的k 1s。
注意：子序列前可能有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，第二个参数应具有type 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;
原则上，如何计算并不重要。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句