使用递归直接输出结果的最大连续子阵列

Question

可以使用递归找到最大的sum连续子数组，这样函数将直接返回输出。

下面是我的解决方案，其中我在每个索引处存储最大子数组结尾，然后在print（）函数中找到最大子数组。不过，我想下面的

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

我的代码使用递归函数和助手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功能，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) 
  } 
  

事实上，你原来我们的解决方案辅助函数可以使你的算法更清晰。

Answer 2

引入两个全局变量start_idx和end_idx来跟踪最大连续子数组的开始和结束索引。在递归函数中相应地更新这些变量。

#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 fun(int n); 
int max(int a, int b); 
int find_max(int a[], int len); 
void print_array(int a[], int start_idx, int end_idx); 

int start_idx = 0; // Start of contiguous subarray giving max sum 
int end_idx = 0; // End of contiguous subarray giving max sum 

#define NEG_INF (-100000) 

int max_sum = NEG_INF; // The max cont sum seen so far. 

int main(void) 
{ 
    start_idx = 0; 
    end_idx = len - 1; 
    maxherearray[0] = a[0]; 

    printf("Array a[]: "); 
    print_array(a, 0, len-1); 
    printf("\n"); 

    // Compute the necessary information to get max contiguous subarray 
    fun(len - 1); 
    printf("Max subarray value == %d\n", find_max(maxherearray, len)); 
    printf("\n"); 

    printf("Contiguous sums: "); 
    print_array(maxherearray, 0, len - 1); 
    printf("\n"); 

    printf("Contiguous subarray giving max sum: "); 
    print_array(a, start_idx, end_idx); 
    printf("\n\n"); 

    return 0; 
} 

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

    int max_till_j = fun(n - 1); 

    // Start of new contiguous sum 
    if (a[n] > a[n] + max_till_j) 
    { 
     maxherearray[n] = a[n]; 

     if (maxherearray[n] > max_sum) 
     { 
      start_idx = end_idx = n; 
      max_sum = maxherearray[n]; 
     } 
    } 
    // Add to current contiguous sum 
    else 
    { 
     maxherearray[n] = a[n] + max_till_j; 

     if (maxherearray[n] > max_sum) 
     { 
      end_idx = n; 
      max_sum = maxherearray[n]; 
     } 
    } 

    return maxherearray[n]; 
} 

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

// Print subarray a[i] to a[j], inclusive of end points. 
void print_array(int a[], int i, int j) 
{ 
    for (; i <= j; ++i) { 
     printf("%d ", a[i]); 
    } 
} 

int find_max(int a[], int len) 
{ 
    int i; 
    int max_val = NEG_INF; 
    for (i = 0; i < len; ++i) 
    { 
     if (a[i] > max_val) 
     { 
      max_val = a[i]; 
     } 
    } 

    return max_val; 
}