largest sum contiguous sub array using recursion to directly output result

Question

Is is possible to find the largest sum contiguous sub array using recursion such that the function would directly return the output.

Below is my solution where I store the max subarray ending at each index and then find the largest among those in the print() function. However, I want the following

1. Use recursion
2. Use the recursive function to directly output the final result.

My code which uses a recursive function and a helper print() function to find the largest among those numbers

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

EDIT : Posting the print() function which I somehow missed out

//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

Generally, your algorithm logic is OK. It's like,

1. f(0) = a(i);
2. f(i) = max(f(i-1) + a(i), a(i));, get the middle result array
3. max(0, f(1), f(2), ... , f(n-1)), get the final max_sub result

And you designed a function namedfun for #2, and a helper print() for #3.

Now, (I guess ) what you'd like is to combine #2 and #3 together, i.e., to utilise the middle results of #2 to avoid extra computing/memory space. In terms of your original algorithm logic, here are some possible ways, such as

• Add a parameter in your fun to keep max_sub result

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

• Use a global variable (Oh!) to get max_sub in time

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

In fact, your original solution of using a helper function can make your algorithm more clear.