Design a divide and conquer algorithm to calculate the maximum sum of any sub array in a given $($not in

general sorted$)$ array of integers. A sub array is a contiguous set of elements in an array, so for example

$(2,4,4,5)$ is a sub array of the array $(3,2,4,4,5,7)$ but $(3,4,5)$ is not. We will assume that your

sub array is not allowed to be empty.

Use the divide and conquer approach to design an O$($n log n$)$ time algorithm. Argue why your algo$-$

rithm is correct and briefly justify the bound on its run$-$time. We will soon $($in the next week$)$ learn about

Dynamic Programming, which will actually let us design an O$($n$)$ time algorithm!

Solution: