largest sum contiguous sub array using recursion to directly output result

2
votes

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;
}
2
carraysrecursiondynamic-programmingcontiguous
Could you paste your print helper function? – Eric Tsui
I can't understand what does maxherearray[i] store in your program ? does it store the largest sum of contigious elements up to i inclusively? for instance, in your example, maxherearray[6] is 7 and maxherearray[7] is 4, so for i=6 it is true but for i=7 it is not – mangusta
what's the point of keeping this array if you cannot tell where the max-sum sequence starts and ends – mangusta

2 Answers

2
votes

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.

1
votes

Introduce two global variables, start_idx and end_idx to track the start and end indices of the largest contiguous subarray. Update these variables accordingly in the recursive function.

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