用递归直接输出结果的最大和邻接子数组

Question

null

我的代码使用一个递归函数和一个helper 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

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

1. F(0)=a(i)；
2. f(i)=max(f(i-1)+a(i)，a(i))；，获取中间结果数组
3. max(0,f(1)，f(2)，...，f(n-1))，获取最终的max_sub结果

您为#2设计了一个名为fun的函数，为#3设计了一个名为print()的助手。

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);
}     

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)
}