A hungry monkey is shown a line of banana clusters, represented as a $1-$indexed array of integers A of length n$.$ Positive numbers in A represent the number of bananas in that cluster, while

negative numbers mean that the monkey has to return some number of bananas. The monkey is

allowed to start at some position $1<=$ i $<=$ n$,$ collecting and$/$or returning bananas up to some index

j $>=$ i without skipping indices. For example, given the array A $=[16,2,10,2,43,20],$ the

monkey$$s best course of action would be to start at position $1$ and stop at position $3.$ The total

number of bananas gained would be $16+(2)+10=24.$

Design an efficient Divide & Conquer algorithm to find the maximum amount of bananas the

monkey can collect. Justify correctness of your algorithm, provide a recurrence, and prove its

runtime.