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

Use recursion
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;
}

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
– mangusta, Commented Jul 10, 2015 at 3:56
what's the point of keeping this array if you cannot tell where the max-sum sequence starts and ends — mangusta
– mangusta, Commented Jul 10, 2015 at 4:27

Eric Tsui · Accepted Answer · 2015-07-10 05:24:17Z

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

f(0) = a(i);
f(i) = max(f(i-1) + a(i), a(i));, get the middle result array
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.

lightalchemist · Accepted Answer · 2015-07-10 03:26:43Z

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

Collectives™ on Stack Overflow

largest sum contiguous sub array using recursion to directly output result

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related