You are given a an array A [1..n] of numbers (which can be positive, 0 or negati

Question

You are given a an array A [1..n] of numbers (which can be positive, 0 or negative). You need to design an algorithm that finds a contiguous subsequence of A with largest sum (This is just a restatement of Problem 2(a) in Jeff Erickson's Lecture 5.) For example given the array [-6, 12, -7, 0, 14, -7, 5), the contiguous subsequence [12, -7, 0, 14] has the largest sum, 19 (a) For 0 lessthanorequalto j lessthanorequalto n, let S(1, j) denote the largest sum of a contiguous subsequence from A [1..j], such that the contiguous subsequence includes A For 0 lessthanorequalto j lessthanorequalto n, let S(2, j) denote the largest sum of a contiguous subsequence from A[l..j]. Write down recurrences for S(1, j) and S(2, j). Make sure that you take care of all the base cases (b) The recurrence from (a) can be implemented as a recursive function, though you don't need to do this. Now think about the memoized version of this recursive function using a 2-dimensional 2 times (n+1) table in which the table-slot Table [i, j] is filled with S (i, j), where i Elementof {1, 2} and 0 lessthanorequalto j lessthanorequalto n. Figure out the order in which this table in filled and then write pseudocode for a function that finds and returns the largest sum of a contiguous subsequence of A [1..n] (c) Write a function that takes as input A and Table (filled out using the function in (b)) and returns the optimal contiguous subsequence from A[1..n].

Explanation / Answer

Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray 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.

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

Time Complexity: maxSubArraySum() is a recursive method and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + (n)

Using Master method. It falls in case II of Master Method and solution of the recurrence is (nLogn).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.