c - 最大和连续子数组使用递归直接输出结果

Question

是否可以使用递归找到最大和的连续子数组，以便函数直接返回输出。

下面是我的解决方案，我存储以每个索引结尾的最大子数组，然后在 print() 函数中找到最大的子数组。但是，我想要以下内容

使用递归

使用递归函数直接输出最终结果。

我的代码使用递归函数和辅助 print() 函数来查找这些数字中的最大值

#include <stdio.h>

//int a[] = {-6,60,-10,20};
int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
int len = sizeof(a)/sizeof(*a);
int maxherearray[10];

int main(void)
{
 fun(len-1);
 printf("max sub array == %d\n",print(maxherearray));

 printf("\n");
 return 0;
}

int fun(int n)
{
 if(n==0)
  return a[n];

 maxherearray[n] = max(a[n], a[n]+fun(n-1));
 return maxherearray[n];
}

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

编辑:发布我以某种方式错过的 print() 函数

//Please make sure that #include <limits.h> is added
int print(int a[])
{
 int i = 0;
 int largest = INT_MIN;
 printf("largest == %d\n",largest);

 for(i=0;i<len;i++)
 {
  if(a[i] > largest)
   largest = a[i];
 }
 return largest;
}

Answer 1

一般来说，你的算法逻辑是可以的。就像是，

f(0) = a(i);

f(i) = max(f(i-1) + a(i), a(i)); ，得到中间结果数组

max(0, f(1), f(2), ... , f(n-1)) , 得到最终的 max_sub 结果

你设计了一个名为 fun 的函数用于 #2 和 a helper print()对于#3。

现在，(我猜)您想要的是将 #2 和 #3 组合在一起，即利用 #2 的中间结果来避免额外的计算/内存空间。就你原来的算法逻辑而言，这里有一些可能的方法，例如

在您的 fun 中添加一个参数保持 max_sub 结果

int fun(int n, int *result)// add int *result to return max_sub
    {
      int max_here = 0;
      if(n==0){
         return a[n];
      }

      max_here =  max(a[n],a[n]+fun(n-1, result)); 
      *result  =  max(*result, max_here);

      return max_here; 
     }
//...
int main(void)
{
   int result = 0;
   fun(len-1, &result);
   printf("max sub : %d\n", result);
}     

使用全局变量(哦!)及时获取 max_sub

int g_maxhere = 0;
int fun2(int n)
{
   if(n==0){
      return a[n];
   }

   g_maxhere = max(g_maxhere, max(a[n],a[n]+fun2(n-1)));

   return max(a[n], a[n]+fun2(n-1));
}
//...
int main(void)
{
  fun2(len-1);
  printf("max sub:%d\n",g_maxhere)
} 

事实上，您使用辅助函数的原始解决方案可以使您的算法更加清晰。