Consider the best array slice problem: Given an array A of n integers, indexed from 0...

Transcribed Image Text:

Consider the best array slice problem: Given an array A of n integers, indexed from 0 to n - 1, find indices and r (with ≤r) that maximize the sum T ΣA[i]. i=l When >r, we evaluate this sum as zero. For example, with the input A = [3,-9, 4, -2, 6, -3, -1, 10, -5, 1, -3, 6], the output should be (2,7), because the greatest possible sum is A[2] + A[3] + A[4] + A[5] + A[6] + A[7] 4+(-2) +6+(-3)+(-1)+10. Best slices are not necessarily unique, and if the array entries are all negative, then the best slices will have l>r. Notice that a best slice could be in the first half in the array (l<r <n/2), in the second half of the array (n/2 ≤ ≤r), or split between the two halves (l<n/2 ≤r). (a) Design a O(n)-time algorithm to find the best slice that is split between the two halves. (b) Design a O(n log n)-time divide-and-conquer algorithm to find the overall best slice. Consider the best array slice problem: Given an array A of n integers, indexed from 0 to n - 1, find indices and r (with ≤r) that maximize the sum T ΣA[i]. i=l When >r, we evaluate this sum as zero. For example, with the input A = [3,-9, 4, -2, 6, -3, -1, 10, -5, 1, -3, 6], the output should be (2,7), because the greatest possible sum is A[2] + A[3] + A[4] + A[5] + A[6] + A[7] 4+(-2) +6+(-3)+(-1)+10. Best slices are not necessarily unique, and if the array entries are all negative, then the best slices will have l>r. Notice that a best slice could be in the first half in the array (l<r <n/2), in the second half of the array (n/2 ≤ ≤r), or split between the two halves (l<n/2 ≤r). (a) Design a O(n)-time algorithm to find the best slice that is split between the two halves. (b) Design a O(n log n)-time divide-and-conquer algorithm to find the overall best slice.

Answer rating: 100% (QA)

To solve the best array slice problemwe can use the ... View the full answer