c - 找到最长的非递减子序列

Question

给定一个字符串只包含 0 和 1 说10101
如何找到最长的非递减子序列的长度？
例如，

对于字符串，
10101

最长的非递减子序列是

• 111
• 001
  所以你应该输出 3

对于字符串
101001

最长的非递减子序列是

• 0001

所以你应该输出 4
如何找到这个？

当我们受到限制时，如何做到这一点。限制之间的序列
例如
101001
限制 [3,6]
最长的非递减子序列是

• 001
  所以你应该输出 3

这可以在 o(strlen) 中实现吗

Answer 1

使用动态规划。从左到右遍历字符串，并跟踪两个变量：

• zero: 以 0 结尾的最长子序列的长度
• one: 以 1 结尾的最长子序列的长度

如果我们看到一个 0，我们可以将它附加到任何以 0 结尾的前缀，所以我们增加zero. 如果我们看到一个 1，我们可以将它附加到以 0 或 1 结尾的前缀上，因此我们设置one最长的那个。在 C99 中：

int max(int a, int b) {
  return a > b ? a : b;
}

int longest(char *string) {
  int zero = 0;
  int one = 0;
  for (; *string; ++string) {
    switch (*string) {
      case '0':
        ++zero;
        break;
      case '1':
        one = max(zero, one) + 1;
        break;
    }
  }
  return max(zero, one);
}

Answer 2

这可以实现O(strlen)吗？

是的。观察到非递减子序列将具有以下三种形式之一：

0........0 // Only zeros
1........1 // Only ones
0...01...1 // Some zeros followed by some ones

前两种形式可以很容易地O(1)通过计数全零和计数全1来签入。

最后一个有点难：你需要遍历字符串，保持你到目前为止看到的零计数器，以及你0...01...1迄今为止发现的最长形式字符串的长度。在您在字符串中看到的每一步，1第三种形式的最长子序列的长度是零的数量加 1 或0...01...1您迄今为止看到的最长序列加 1 中的较大者。

以下是上述方法在 C 中的实现：

char *str = "10101001";
int longest0=0, longest1=0;
for (char *p = str ; *p ; p++) {
    if (*p == '0') {
        longest0++;
    } else { // *p must be 1
        longest1 = max(longest0, longest1)+1;
    }
}
printf("%d\n", max(longest0, longest1));

max定义如下：

#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )

这是ideone 上演示的链接。

Answer 3

do {
    count++;
    if (array[i] < prev) {
        if (count > max)
            max = count;
        count = 0;
    }
    prev = array[i];
} while (++i < length);

单程。甚至可以处理任何数字，而不仅仅是 1 和 0。

对于限制 - 设置i为起始编号，使用结束而不是数组长度。