Please explain me how this answer will come step by step

Quiz 4: Divide-and-Conquer Question 1 47 out of 50 points Let A[1n] be an array of n positive and negative numbers. The minimum subarray of A is a contiguous subarray of A which has the smallest sum. Please give the divide-and-conquer algorithm to compute the sum of the minimum subarray of A in O(nlog n) time. For example, if the given array is {-3, 5, -2, 1, -4, -7, 9, -6, 2}, then the minimum subarray of A is {-2, 0, -4, -7} and the output is their sum -13. Please briefly describe your idea, give pseudocode if necessary, give the recurrence and conclude the time complexity. You do not need to show how to solve the recurrence to get the running time complexity. Selected Answer: [None Given] Correct Answer: Answer 1: We can model this minimum subarray problem as a maximum subarray problem: we create an array B of size n and let B[i] = -A[i] for every 1 sum // If minsum_R is larger than sum, we meet a smaller subarray A[m+1, , i]; otherwise, we continue. minsum_R = sum } // The following is computing the minimum subarray of A[L, , m] ending with A[m] minsum_L = + sum = 0 for i = m down to L { sum = sum +A[i] if minsum_L > sum minsum_L = sum } //the minimum crossing subarray of A[L, , R] is the concatenation of the two above computed minimum subarrays and so its sum is (minsum_R+minsum_L) return (minsum_R+minsum_L) } Correctness: the minimum subarrary of A could entirely lie in the left half A[L, , m], entirely in the right half A[m+1, , R], or contain numbers of both halves, i.e., the middle position A[m]. We respectively compute the minimum subarray of A[L, , m], the minimum subarray of A[m+1, , R], and the minimum subarray of A[L, , R] crossing A[m]. It is obvious that the minimum subarray of A[L, , R] is the one of the three which has the smallest sum. Thus, our algorithm can correctly compute the minimum subarray sum of A[L, , R]. Running time: Min-Cross-Subarray(A, L, m, R) takes O(n) time. The recurrence of Min-subarray(A, L, R) is for n>1 and T(1) = 1. The recurrence is same to MergeSort's and so the time complexity is O(nlog n).

uiz 4: Divide-and-Conquer lestion 1 47 out of 50 points et A[1n] be an array of n positive and negative numbers. The minimum subarray of A a contiguous subarray of A which has the smallest sum. Please give the divide-andonquer algorithm to compute the sum of the minimum subarray of A in O(nlogn) time. or example, if the given array is {3,5,2,1,4,7,9,6,2}, then the minimum subarray fA is {2,0,4,7} and the output is their sum 13. lease briefly describe your idea, give pseudocode if necessary, give the recurrence and onclude the time complexity. You do not need to show how to solve the recurrence to et the running time complexity. elected [None Given] Answer 1: We can model this minimum subarray problem as a maximum subarray problem: we create an array B of size n and let B[i]=A[i] for every 1sum//addA[i]tovaraiblesumtocompute//Ifminsum.Bislargerthansum,we meet a smaller subarray A[m+1,,i]; otherwise, we continue. \} minsum R= sum // The following is computing the minimum subarray of A[L,,m] ending with A[m] minsum L=+ sum =0 for i=m down to L \{ sum = sum +A[1] if minsum L> sum minsum L sum \} //the minimum crossing subarray of A[L,,R] is the concatenation of the two above computed minimum subarrays and so its sum is (minsum R+minsum_L ) return (minsum R+ minsum L ) \} Correctness: the minimum subarrary of A could entirely lie in the left half A[L,, ,m], entirely in the right half A[m+1,,R], or contain numbers of both halves, i.e., the middle position A[m]. We respectively compute the minimum subarray of A[L,,m], the minimum subarray of A[m+1,,R], and the minimum subarray of A[L,,R] crossing A[m]. It is obvious that the minimum subarray of A[L,,R] is the one of the three which has the smallest sum. Thus, our algorithm can correctly compute the minimum subarray sum of A[L, ,R]. Running time: Min-Cross-Subarray (A,L,m,R) takes O(n) time. The recurrence of Min-subarray (A,L,R) is for n>1 and T(1)= 1. The recurrence is same to MergeSort's and so the time complexity is O(nlog n)