Question

8. (1) Implement the minimum subsequence sum using divide-and-conquer. (30 points) (2) For the array =[4-3 5-2-1 2 6-2, you should provide the solution using the minimum subsequence sum like the example in class. Test the sample for your code. (3) Obtain the T(n) expression for the above algorithm

Answer 1

1.ans-:step 1) Divide a given array in two halves

step 2) Returning the maximum of following three
a) Maximum subsequence sum in left half (Make a recursive call)
.b) Maximum subsequence sum in right half (Make a recursive call)
c) Maximum subsequence sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subsequence sum such that the subsequence crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.

2.Ans-:

#include <stdio.h>

#include <limits.h>

  

// A utility funtion to find maximum of two integers

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

  

// A utility funtion to find maximum of three integers

int max(int a, int b, int c) { return max(max(a, b), c); }

  

// Find the maximum possible sum in arr[] auch that arr[m] is part of it

int maxCrossingSum(int arr[], int l, int m, int h)

{

// Include elements on left of mid.

int sum = 0;

int left_sum = INT_MIN;

for (int i = m; i >= l; i--)

{

sum = sum + arr[i];

if (sum > left_sum)

left_sum = sum;

}

  

// Include elements on right of mid

sum = 0;

int right_sum = INT_MIN;

for (int i = m+1; i <= h; i++)

{

sum = sum + arr[i];

if (sum > right_sum)

right_sum = sum;

}

  

// Return sum of elements on left and right of mid

return left_sum + right_sum;

}

  

// Returns sum of maxium sum subarray in aa[l..h]

int maxSubArraySum(int arr[], int l, int h)

{

// Base Case: Only one element

if (l == h)

return arr[l];

  

// Find middle point

int m = (l + h)/2;

  

/* Return maximum of following three possible cases

a) Maximum subarray sum in left half

b) Maximum subarray sum in right half

c) Maximum subarray sum such that the subarray crosses the midpoint */

return max(maxSubArraySum(arr, l, m),

maxSubArraySum(arr, m+1, h),

maxCrossingSum(arr, l, m, h));

}

  

/*Driver program to test maxSubArraySum*/

int main()

{

int arr[] = {4, -3, 5, -2, -1,2,6,-2};

int n = sizeof(arr)/sizeof(arr[0]);

int max_sum = maxSubArraySum(arr, 0, n-1);

printf("Maximum contiguous sum is %dn", max_sum);

getchar();

return 0;

}

3.Ans-:time complexity of algorithm can be expressed as following recurrence relation.

T(n) = 2T(n/2) + Θ(n)