Write a program in C that implements the algorithm on pp. 71 and 72 (shown below, from Introduction to Algorithms, 3rd Edition, by Cormen et al) for solving the maximum subarray problem. Use as inputs three different arrays of size 16: one with all positive entries, and the other two with a mix of positive and negative entries. Submit the program, the inputs and the outputs. These are the only directions I have.

CODE ONE (From page 71) *****************************************************

CODE TWO (From page 72) **************************************************************

FIND-MAX-CROSSING-SUBARRAY (A, low, mid, high) 1 left-sum 2 sum -0 3 fori - mid downto low 4 5 if sum > left-sum - -oo sum - sum Ali] left-sum sum max-left i 7 8 right-sumoo 10 for j mid +1 to high 11sum-sum Alj] 12 if sum > right-sum 13 14 right-sum - sum max-right - j 15 return (max-left, max-right, left-sum +right-sum) FIND-MAXIMUM-SUBARRAY (A, low, high) 1 if highlow 2return (low, high, A[low]) 3 else mid - [(low + high)/2 4(lefi-low, left-high, left-sum) - 2 return (low, high, // base case: only one element FIND-MAXIMUM-SUBArRAY (A, low, mid) (right-low , right-high, right-sum) FIND-MAXIMUM-SUBARRAY (cross-low, cross-high, cross-sum) (A, mid 1,high) FIND-MAX-CROSSING-SUBARRAY (A, low, mid, high) 7 if left-sum right-sum and left-sum cross-sunm return (left-low, left-high, left-sum) 9 elseif right-sum > left-sum and right-sum 10 cross-sum return (right-low, right-high, right-sum) 11else return (cross-low, cross-high, cross-sum)