Problem $3.(15+5=19$ points$)$ Help thy neighbor

$2023$ was a tough year for the Red Sox. Looking to find some silver linings in the difficult season,

manager Alex Cora has asked you to help identify the best stretch of the season for the team. To

do this, the analytics department has shared with you the run differentials from $n$ games this

season. For each game, this value can be positive $($if the Sox won$)$ or negative $($if they lost$).$ For

example, if they won $10-4,$ then lost $6-2,$ then won $3-2,$ the run differentials would be $6,-4,1.$

Alex would like you to find the stretch of consecutive games such that the total run differential

is maximized. The total run differential of a stretch of games is simply the sum of the run

differentials of those games.

For example, consider the following:

$n=7,$ differentials: $-1,5,-2,1,4,-3,1$

Here, the optimal solution is from game $2$ to game $5,$ and the total run differential is $8.$

$($a$)$ Write $($in pseudocode$)$ a divide and conquer algorithm which solves this problem in

$O(nlogn)$ time. Provide a few sentences describing your approach. Note that your

algorithm should output the range of games that yields the maximum total run differential.