$1.$ Maximum Subarray Problem $(10$ marks$)$

Description: Given an array of integers, find the contiguous subarray which has the largest sum.

Pseudocode:

function maxSubArray$($A$,$ left, right$)$

if left $==$ right

return A$[$left$]$

mid $=($left $+$ right$)/2$

left$\_$max $=$ maxSubArray$($A$,$ left, mid$)$

right$\_$max $=$ maxSubArray$($A$,$ mid$+1,$ right$)$

cross$\_$max $=$ maxCrossingSum$($A$,$ left, mid, right$)$

return max$($left$\_$max, right$\_$max, cross$\_$max$)$

Question: Implement the maxCrossingSum function used in the pseudocode above and test your

function with the array $[-2,1,-3,4,-1,2,1,-5,4].$