c - 使用递归查找具有相同数量的 0's and 1' 的最大子数组的长度

Question

给定一个只有 0's 的数组和 1's找到具有相同数量 0's 的最大子数组的长度和 1's .例如，给定一个数组

011110001

0's个数相等的最大子数组和 1's长度为 8，从索引 0 到索引 7。

写一个递归函数largestSubarray .该函数有 3 个输入:一个数组 - A，它的第一个元素的索引 - 开始，它的最后一个元素的索引 - 结束，并返回最大子数组的大小。如果没有相同数量的子数组 0's and 1's找到，该函数应返回 0。

int largestSubarray(int * A, int start, int end){
  int i, j=0, k=0;
  for(i=start; i<=end; i++){
    if(arr[i]==0){
     j++;
    }
    else if(arr[i]==1){
     k++;
    }
    if (j==k){
return (end+1-start)+largestSubarray(array, start+1, end);
    }

   }

如何修复此代码？请帮忙。谢谢。

Answer 1

不清楚您是否解决了问题。递归可以为那些特别适合的任务或无法合理编写过程解决方案的任务提供优雅的解决方案。每个递归调用都是一个单独的函数调用，需要一个完整的单独函数堆栈。随着递归次数的增加，这会迅速耗尽可用内存。应首选程序解决方案。

此外，您的数组 011110001 必须是包含值的数组的简写

0, 1, 1, 1, 1, 0, 0, 0, 1

011110001 本身是 2396161 的八进制常量。

在这里，找到由 0 和 1 组成的最大平衡子数组可以像使用循环一样轻松地完成。然而，了解这是一道练习题，它具有教育值(value)。

一个干净的解决方案是编写一个 largestsubarray 包装函数来调用第二个递归函数，将 size 的整数指针作为内部调用的额外参数。通过提供单个地址保持大小，您可以消除递归展开时值被覆盖的可能性。

在单个函数中，关键是强制每个递归调用返回，否则您将在递归函数展开时遇到覆盖 size 的问题。一种实现可能是:

/* end must be ending index -- not size */
int largestsubarry (int *a, int start, int end)
{
    int o = 0, z = 0;       /* ones, zeros */

    if (end <= start)
        return 0;

    /* count the ones and zeros in subarray */
    for (register int i = start; i <= end; i++) {
        if (a[i] == 1)
            o++;
        else if (a[i] == 0)
            z++;
        else
            o = z = 0;      /* reset on any other value */
    }

    if (o != z) {   /* ones & zeros not equal */
        int s = largestsubarry (a, start + 1, end), /* test eliminating */
            e = largestsubarry (a, start, end - 1); /* each end */

        if (s > e)  /* return largest */
            return s;
        else
            return e;
    }
    else    /* balanced sub-array found, return size */
        return o + z;
}

(注意虽然不是错误，但 C 的标准编码风格避免使用 camelCase 或 MixedCase 变量名所有小写，同时保留大写名称用于宏和常量。这是一个风格问题——所以这完全取决于你，但不能遵循它可能会在某些圈子中导致错误的第一印象。)

示例使用/输出

传递包含以下值的整数数组会导致找到连续 0 和 1 的最大平衡子数组的适当大小，例如

$ ./bin/subarray
enter array (ctrl+d ends): 0 1 1 1 1 0 0 0 1
size: 8

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 1 1 1 0 0 0 1
size: 8

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 1 1 1 0 0 0 1 0
size: 10

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 0 0 0 0 0 0 1
size: 6

$ ./bin/subarray
enter array (ctrl+d ends): 0 2 2 2 2 0 0 0 2
size: 0

可能有更有效的方法，但关键是知道要消除哪一端才能找到最长的平衡子数组。