3. (20 pts) With a sly wink, Dumbledore says his real goal was actually to calcu

Question

3. (20 pts) 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(n logn) 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 find the largest subarray sum for the left half . Recursively find 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 On the chalkboard, which appears out of nowhere in a gentle puff of smoke, Hagrid writes the following pseudocode for his algorithm: hagridSolve(A) f if (A.lengthO) return 0 return hagHelp(A,1,A.lengthO) hagHelp (A, s, t) if (s > t) 1 return 0 if (s - t) 1 return max (0, A[s])

Explanation / Answer

The loop for leftmax calculation should be :

for(i=m; i>=s ; i--)

instead of

for(i=m; i>s ; i--)

since the array has a startindex of 1.

Moreover loop for rightmax calculation should be

for(i=m+1; i<=t ; i++)

instead of

for(i=m; i<=t ; i++)

otherwise A[m] will be considered twice ( first in leftmax and then in rightmax).

The recurrence relation will be:-

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

Hence the running time will be O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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