1) Use the following input vector to find maximum sub vector. Step into the pseudocode on slide 17 and 19 and show your stepping in neatly. At the least show the following, every step of recursion and following return values when returning from the recursions and find-max-crossing-subarray function. left-low, left-high, left-sum right-low, right-high, right-sum cross-low, cross-high, cross-sum 0 31 1 2 -41 59 3 26 4 -53 5 6 58 97 7 -93 8 -23 9 84 2) Mark in the given code the steps: Divide, Conquer, and Combine. 3) A problem similar to that of the maximum subvector is that of the maximum increasing subvector of a vector containing both positive and negative values. An increasing subvector is a slice of an array consisting of strictly increasing values. More precisely, such a subvector will begin at some index i, end at index j, and for any index k, i k < j, A[k] FIND-MAXIMUM-SUBARRAY (A, low, high) if high == low return (low, high, A[low]) else mid= [(low + high)/2] (left-low, left-high, left-sum) = 1 2 3 4 5 6 7 8 9 10 11 FIND-MAXIMUM-SUBARRAY (A. low, mid) (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY (A, mid+ 1, high) (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY (A, low, mid, high) 10 11 12 13 if left-sum right-sum and left-sum > cross-sum return (left-low, left-high, left-sum) elseif right-sum > left-sum and right-sum > cross-sum return (right-low, right-high, right-sum) else return (cross-low, cross-high, cross-sum) FIND-MAX-CROSSING-SUBARRAY (A, low, mid, high) left-sum0 1 2 sum = 0 3 for i 4 5 6 7 8 9 mid downto low sum + A[i] sum if sum left-sum //base case: only one element left-sum = sum max-lefi = i right-sum sum = 0 for j = mid + 1 to high sum sum + A[j] if sum > right-sum right-sum = sum max-right = j 14 15 return (max-left, max-right, left-sum + right-sum)