CODEWITHSUNDEEP
calgorithm
user4018473
user4018473

Reputation: 77

Understanding a recursive function

int Max_Subarray_Sum(int arr[], int n)  
{
    if(n == 1)
    {
        return arr[0];   // what it will be return for right Sub array
    }
    int m = n / 2;
    int left_MSS = Max_Subarray_Sum(arr, m);
    int right_MSS = Max_Subarray_Sum(arr + m, n - m);  // why arr+m will d0
    int leftsum = INT_MIN, rightsum = INT_MIN, sum = 0;
    for(int i = m; i < n; i++)
    {
        sum += arr[i];
        rightsum = max(rightsum, sum);
    }
    sum = 0;
    for(int i = (m-1); i >= 0; i--)
    {
        sum += arr[i];
        leftsum = max(leftsum,sum);
    }
}

I can't understand this piece of code, what will arr+m will do. Please help me.
Thanks in advance.

Upvotes: 1

Views: 96

Answers (3)

Dr. Debasish Jana
Dr. Debasish Jana

Reputation: 7128

Corrected function:

int Max_Subarray_Sum(int arr[],int n)   
{
  if(n==1)
  {
    return arr[0];   // what it will be return for right Sub array
  }
  int m = n/2;
  int left_MSS = Max_Subarray_Sum(arr,m);
  int right_MSS = Max_Subarray_Sum(arr+m,n-m);  // why arr+m will d0
  return left_MSS + right_MSS;        
}

Explanation: Say, 1st Call: Max_Subarray_Sum({4, 2, 5}, 3)

Max_Subarray_Sum({4, 2, 5}, 3)
= Max_Subarray_Sum({4}, 1) + Max_Subarray_Sum({2, 5}, 2)
= 4 + Max_Subarray_Sum({2}, 1) + Max_Subarray_Sum({5}, 1)
= 4 + 2 + 5
= 11

Upvotes: 0

mch
mch

Reputation: 9814

int Max_Subarray_Sum(int arr[],int n)
{
    if(n==1)
    {
        return arr[0];   // what it will be return for right Sub array
    }
    int m = n/2;
    int left_MSS = Max_Subarray_Sum(arr,m);
    int right_MSS = Max_Subarray_Sum(arr+m,n-m);  // why arr+m will d0
    return left_MSS + right_MSS;
}

this should work. You forgot to add the last return. I also removed the for loop since its results will be thrown away. this function splits the array into subarrays until it contains only 1 value.

Upvotes: 0

amit
amit

Reputation: 178521

you can think of arr as a pointer to starting point of an array of integers. arr + m means the address of the mth element in the array, so this is basically splitting the array into two parts:

invoke recursive function on first m elements of the array:

int left_MSS = Max_Subarray_Sum(arr,m);

invoke recursive function on last n-m elements of the array:

int right_MSS = Max_Subarray_Sum(arr+m,n-m);

Upvotes: 1

Related Questions