With a sly wink, Dumbledore says his real goal was actually to calculate and return the largest value in the matrix B, that is, the largest subarray sum in A. Butting in, Professor Hagrid claims to know a fast divide and conquer algorithm for this problem that takes only O(nlogn) time (compared to applying a linear search to the B matrix, which would take O(n2) time).

Hagrid says his algorithm works like this:

Divide the array A into left and right halves

Recursively nd the largest subarray sum for the left half

Recursively nd the largest subarray sum for the right half

Find largest subarray sum for a subarray that spans between the left and right halves

Return the largest of these three answers

Following is a pseudocode of his plan:

hagridSolve(A) {

if(A.length()==0) { return 0 }

return hagHelp(A,1,A.length())

} hagHelp(A, s, t) {

if (s > t) { return 0 }

if (s == t) { return max(0, A[s]) }

m = (s + t) / 2

leftMax = sum = 0

for (i = m, i > s, i--) {

sum += A[i]

if (sum >= leftMax) { leftMax = sum }

} rightMax = sum = 0

for (i = m, i <= t, i++) {

sum += A[i]

if (sum > rightMax) { rightMax = sum }

} spanMax = leftMax + rightMax

halfMax = max( hagHelp(s, m), hagHelp(m+1, t) )

return max(spanMax, halfMax) }

(i) Identify and x the errors in Hagrids code,

(II) Prove that the corrected algorithm works

PART (3-4) OF THIS PROBLEM IS POSTED ON ANOTHER THREAD