用递归法求0和1个数相等的最大子数组的长度

Question

给定一个只有0和1的数组，求取0和1数目相等的最大子数组的长度。例如，给定一个数组

011110001

编写递归函数largestsubarray。这个函数接受3个输入：一个数组-A，它的第一个元素的索引-start，最后一个元素的索引-end，并返回largestsubarray的大小。如果没有找到0和1数量相等的子数组，则函数应返回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的八进制常数。

在单个函数中，关键是强制返回每个递归调用，否则当递归函数展开时，您将遇到覆盖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

也许有更有效的方法来做这件事，但关键是知道要消除哪一端才能找到最长的平衡子数组。